Submission #952320

#TimeUsernameProblemLanguageResultExecution timeMemory
952320serifefedartarUntitled (POI11_rot)C++17
72 / 100
239 ms65536 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define fast ios::sync_with_stdio(0);cin.tie(0); typedef long long ll; #define f first #define s second #define LOGN 20 const ll MOD = 998244353; const ll MAXN = 2e5 + 100; vector<vector<int>> graph; tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> st[MAXN]; int now = 0; ll ans = 0; int dfs() { int q; cin >> q; if (q == 0) { int x = dfs(); int y = dfs(); if (st[y].size() > st[x].size()) swap(x, y); ll all = st[x].size() * 1LL * st[y].size(); ll nw = 0; for (auto u : st[y]) nw += st[x].order_of_key(u); for (auto u : st[y]) st[x].insert(u); ans += min(nw, all - nw); return x; } else { now++; st[now].insert(q); return now; } } int main() { fast int leaves; cin >> leaves; dfs(); cout << ans << "\n"; }
#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...