Submission #5559792
Source Code Expand
#pragma GCC optimize ("-O3") #include <bits/stdc++.h> #include<unordered_map> using namespace std; using VS = vector<string>; using LL = long long; using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; using PLL = pair<LL, LL>; using VL = vector<LL>; using VVL = vector<VL>; #define ALL(a) begin((a)),end((a)) #define RALL(a) (a).rbegin(), (a).rend() #define SZ(a) int((a).size()) #define SORT(c) sort(ALL((c))) #define RSORT(c) sort(RALL((c))) #define UNIQ(c) (c).erase(unique(ALL((c))), end((c))) #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++) #define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--) #ifdef YANG33 #include "mydebug.hpp" #else #define DD(x) #endif const int INF = 1e9; const LL LINF = 1e16; const LL MOD = 1000000007; const double PI = acos(-1.0); int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 }; int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 }; /* ----- __MAKE_TIME__ Problem: __PROBLEM__ / Link: __CONTEST_URL__ ----- */ template <class N, class E> struct Rerooting { int n; const vector<vector<E>>& G; vector<N> subtreesum; vector<vector<N>> dp; // L vector<unordered_map <int, N>>edgememo; void dfs1(int v, int p) { subtreesum[v] = N(); for (auto e : G[v]) { int nx = e.to; if (nx == p) continue; dfs1(nx, v); subtreesum[v] = subtreesum[v] + subtreesum[nx].include_e(v, e); } subtreesum[v] = subtreesum[v].include_v(v); } void dfs2(int v, int p, N top) { int deg = int(G[v].size()); dp[v] = vector<N>(deg + 1); dp[v][0] = N(); for (int i = 0; i < deg; i++) { int nx = G[v][i].to; dp[v][i + 1] = dp[v][i] + (nx == p ? top : subtreesum[nx]).include_e(v, G[v][i]); } N rnode = N(); dp[v].back() = dp[v].back().include_v(v); for (int i = deg - 1; i >= 0; i--) { dp[v][i] = (dp[v][i] + rnode).include_v(v); int nx = G[v][i].to; edgememo[v][nx] = dp[v][i]; if (nx != p)dfs2(nx, v, dp[v][i]); rnode = rnode + (nx == p ? top : subtreesum[nx]).include_e(v, G[v][i]); } } Rerooting(const vector<vector<E>>& _g, int root) : n(int(_g.size())), G(_g), subtreesum(n), dp(n), edgememo(int(_g.size())) { dfs1(root, -1); dfs2(root, -1, N()); } }; template <class N, class E> vector<vector<N>> Rerooting_get(const vector<vector<E>>& g, int root) { return Rerooting<N, E>(g, root).dp; } inline int ri() { int in; int y = scanf("%d", &in); return in; } inline LL ril() { LL in; int y = scanf("%lld", &in); return in; } inline void oi(LL out) { printf("%lld\n", out); } int main() { struct Edge { int to; Edge(int t) :to(t) {} }; int N = ri(); vector<vector<Edge>>G(2 * N); vector<PII>edge(N - 1); FOR(i, 0, N - 1) { int a = ri() - 1, b = ri() - 1; G[a].push_back(Edge(b)); G[b].push_back(Edge(a)); edge[i] = PII(a, b); } static string s; cin >> s; struct Node { PLL d; int onecnt; Node() :d(PLL(0, 0)), onecnt(0) {} Node include_e(int, const Edge&) const { Node res = *this; res.d.second = 0; res.d.first++; return res; } Node operator + (const Node& r) const { Node res = *this; for (auto it : { r.d.first,r.d.second }) { if (res.d.first < it) { res.d.second = res.d.first; res.d.first = it; } else if (res.d.second < it) { res.d.second = it; } } res.onecnt += r.onecnt; return res; } Node include_v(int v) const { Node res = *this; if (s[v] == '1')res.onecnt++; return res; } }; auto all_tree = Rerooting<Node, Edge>(G, 0); auto tree_dp_v = all_tree.dp; auto tree_dp_e = all_tree.edgememo; LL ans = 0; // vertex c FOR(i, 0, N) { LL OK = tree_dp_v[i].back().d.second; LL DW = INF; DD(de(tree_dp_v[i].back().d)); for (auto it : tree_dp_v[i]) { if (it.onecnt) DW = min(DW, it.d.first); } if (s[i] == '1')DW = 0; DD(de(OK, DW)); if (DW <= OK) ans += OK - DW + 1; } DD(de(ans)); // edge c FOR(i, 0, N - 1) { int a, b; tie(a, b) = edge[i]; Node d1 = tree_dp_e[a][b]; Node d2 = tree_dp_e[b][a]; DD(de(d1.d, d1.onecnt, d2.d, d2.onecnt)); if (d1.d.first > d2.d.first) { ans += d2.onecnt > 0; } else if (d1.d.first < d2.d.first) { ans += d1.onecnt > 0; } else ans++; } oi(ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Black Radius |
User | Yang33 |
Language | C++14 (GCC 5.4.1) |
Score | 1300 |
Code Size | 4428 Byte |
Status | WA |
Exec Time | 645 ms |
Memory | 205572 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1300 / 1300 | 0 / 600 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt |
Subtask | 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt, 2_44.txt, 2_45.txt, 2_46.txt, 2_47.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 1 ms | 256 KB |
0_01.txt | AC | 1 ms | 256 KB |
0_02.txt | AC | 1 ms | 256 KB |
1_00.txt | AC | 1 ms | 256 KB |
1_01.txt | AC | 528 ms | 205572 KB |
1_02.txt | AC | 532 ms | 195460 KB |
1_03.txt | AC | 479 ms | 177156 KB |
1_04.txt | AC | 589 ms | 177808 KB |
1_05.txt | AC | 541 ms | 178712 KB |
1_06.txt | AC | 471 ms | 177412 KB |
1_07.txt | AC | 471 ms | 177408 KB |
1_08.txt | AC | 478 ms | 179588 KB |
1_09.txt | AC | 509 ms | 189956 KB |
1_10.txt | AC | 496 ms | 185092 KB |
1_11.txt | AC | 525 ms | 202116 KB |
1_12.txt | AC | 478 ms | 176900 KB |
1_13.txt | AC | 522 ms | 188676 KB |
1_14.txt | AC | 493 ms | 180356 KB |
1_15.txt | AC | 471 ms | 179332 KB |
1_16.txt | AC | 493 ms | 183168 KB |
1_17.txt | AC | 520 ms | 187652 KB |
1_18.txt | AC | 470 ms | 175108 KB |
1_19.txt | AC | 469 ms | 175236 KB |
1_20.txt | AC | 479 ms | 174468 KB |
1_21.txt | AC | 483 ms | 178692 KB |
1_22.txt | AC | 472 ms | 176392 KB |
1_23.txt | AC | 468 ms | 176524 KB |
1_24.txt | AC | 587 ms | 177540 KB |
1_25.txt | AC | 606 ms | 181648 KB |
1_26.txt | AC | 452 ms | 172552 KB |
1_27.txt | AC | 594 ms | 176784 KB |
1_28.txt | AC | 584 ms | 178996 KB |
1_29.txt | AC | 487 ms | 183200 KB |
2_00.txt | AC | 1 ms | 256 KB |
2_01.txt | AC | 536 ms | 204420 KB |
2_02.txt | AC | 535 ms | 200068 KB |
2_03.txt | AC | 533 ms | 198532 KB |
2_04.txt | AC | 533 ms | 190852 KB |
2_05.txt | AC | 527 ms | 191236 KB |
2_06.txt | AC | 530 ms | 195460 KB |
2_07.txt | AC | 492 ms | 177156 KB |
2_08.txt | WA | 485 ms | 177156 KB |
2_09.txt | AC | 486 ms | 177156 KB |
2_10.txt | AC | 601 ms | 177808 KB |
2_11.txt | AC | 599 ms | 177808 KB |
2_12.txt | AC | 606 ms | 177808 KB |
2_13.txt | AC | 550 ms | 178712 KB |
2_14.txt | AC | 544 ms | 178712 KB |
2_15.txt | AC | 548 ms | 178712 KB |
2_16.txt | WA | 470 ms | 179460 KB |
2_17.txt | WA | 470 ms | 177412 KB |
2_18.txt | WA | 478 ms | 177412 KB |
2_19.txt | WA | 473 ms | 177412 KB |
2_20.txt | WA | 473 ms | 177412 KB |
2_21.txt | WA | 474 ms | 177540 KB |
2_22.txt | WA | 481 ms | 179332 KB |
2_23.txt | WA | 491 ms | 180608 KB |
2_24.txt | WA | 475 ms | 180100 KB |
2_25.txt | AC | 504 ms | 190852 KB |
2_26.txt | WA | 508 ms | 188292 KB |
2_27.txt | WA | 510 ms | 190848 KB |
2_28.txt | WA | 495 ms | 186112 KB |
2_29.txt | WA | 524 ms | 199940 KB |
2_30.txt | AC | 519 ms | 194180 KB |
2_31.txt | WA | 518 ms | 186756 KB |
2_32.txt | WA | 477 ms | 178052 KB |
2_33.txt | WA | 492 ms | 181888 KB |
2_34.txt | WA | 488 ms | 183556 KB |
2_35.txt | WA | 516 ms | 189956 KB |
2_36.txt | WA | 476 ms | 175108 KB |
2_37.txt | WA | 476 ms | 175620 KB |
2_38.txt | WA | 478 ms | 177668 KB |
2_39.txt | WA | 480 ms | 176640 KB |
2_40.txt | WA | 602 ms | 177552 KB |
2_41.txt | WA | 464 ms | 175492 KB |
2_42.txt | WA | 583 ms | 174480 KB |
2_43.txt | WA | 645 ms | 189316 KB |
2_44.txt | WA | 594 ms | 175376 KB |
2_45.txt | WA | 588 ms | 178076 KB |
2_46.txt | WA | 576 ms | 178328 KB |
2_47.txt | WA | 588 ms | 183372 KB |