Submission #1067319

#TimeUsernameProblemLanguageResultExecution timeMemory
1067319lmaobruhUntitled (POI11_rot)C++14
100 / 100
189 ms40400 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ll long long const int N = 4e5+5, sizeBit = 2e5+5; int ft[sizeBit]; int get(int p) { int tot = 0; for (; p <= N/2; p += p & -p) tot += ft[p]; return tot; } void upd(int p, int v) { for (; p; p -= p & -p) ft[p] += v; } int n, a[N], curr = 1, sz[N], big[N]; vector<int> g[N]; ll ans[N], inv; void read() { int x; cin >> x; if (x) return a[curr] = x, void(); int tmp = curr; g[tmp].pb(++curr); g[curr].pb(tmp); read(); // cay con trai g[tmp].pb(++curr); g[curr].pb(tmp); read(); // cay con phai } void dfs_sz(int u, int pre = -1) { sz[u] = (a[u] > 0); big[u] = 0; for (int v : g[u]) if (v != pre) { dfs_sz(v, u); sz[u] += sz[v]; if (sz[v] > sz[big[u]]) big[u] = v; } } void add_inv(int u, int pre) { if (a[u]) { inv += get(a[u]+1); return; } for (int v : g[u]) if (v != pre) add_inv(v, u); } void add_bit(int u, int pre) { if (a[u]) { upd(a[u], 1); return; } for (int v : g[u]) if (v != pre) add_bit(v, u); } void del(int u, int pre) { if (a[u]) { upd(a[u], -1); return; } for (int v : g[u]) if (v != pre) del(v, u); } void add(int u, int pre) { add_inv(u, pre); add_bit(u, pre); } void dfs(int u, int pre) { if (a[u]) { add(u, pre); return; } int node; for (int v : g[u]) if (v != pre && v != big[u]) { dfs(v, u); ans[u] += ans[v]; del(v, u); node = v; } dfs(big[u], u); ans[u] += ans[big[u]]; inv = 0; add(node, u); ans[u] += min(inv, 1LL * sz[big[u]] * sz[node] - inv); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; read(); dfs_sz(1, 1); dfs(1, 1); cout << ans[1]; }

Compilation message (stderr)

rot.cpp: In function 'void dfs(int, int)':
rot.cpp:92:48: warning: 'node' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |   ans[u] += min(inv, 1LL * sz[big[u]] * sz[node] - inv);
      |                                         ~~~~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...