Submission #952272

#TimeUsernameProblemLanguageResultExecution timeMemory
952272serifefedartarUntitled (POI11_rot)C++17
36 / 100
1103 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[3*MAXN]; int val[3*MAXN], now = 0; ll ans = 0; void construct_tree(int from) { now++; cin >> val[now]; graph[from].push_back(now); if (val[now] == 0) { int q = now; construct_tree(q); construct_tree(q); } else st[now].insert(val[now]); } void dfs(int node, int parent) { for (auto u : graph[node]) { if (u == parent) continue; dfs(u, node); } if (graph[node].size() != 2) return ; int x = graph[node][0]; int y = graph[node][1]; 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); swap(st[x], st[node]); ans += min(nw, all - nw); } int main() { fast int leaves; cin >> leaves; graph = vector<vector<int>>(3*leaves, vector<int>()); construct_tree(0); dfs(0, 0); 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...