Submission #1020426

#TimeUsernameProblemLanguageResultExecution timeMemory
1020426coldbr3wUntitled (POI11_rot)C++17
0 / 100
44 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<long long, long long> #define pb push_back #define F first #define S second #define all(x) (x).begin(), (x).end() const ll N = 1e6 + 100; const ll inf = 1e18; const ll mod = 1e9 + 7; const ll block = 450; ll n, m, res = 0; ll a[N], sz[N], heavy[N]; vector<ll>adj[N]; set<ll>s[N]; struct fenwick_tree{ ll n; vector<ll>ft; void init(ll _n){ n = _n; ft.resize(n + 10); } void update(ll idx, ll val){ while(idx <= n){ ft[idx] += val; idx += (idx & (-idx)); } } ll get(ll idx){ ll res = 0; while(idx > 0){ res += ft[idx]; idx -= (idx & (-idx)); } return res; } } ft; ll idx = 1; void input(){ ll x; cin >> x; a[idx] = x; if(x != 0) return; ll cur = idx; idx++; adj[cur].pb(idx); input(); idx++; adj[cur].pb(idx); input(); } void pre_dfs(ll u, ll par){ sz[u] = 1; for(auto v : adj[u]){ if(v == par) continue; pre_dfs(v, u); sz[u] += sz[v]; if(sz[v] > sz[heavy[u]]) heavy[u] = v; } } void change(ll u, ll par, ll val){ if(a[u] > 0) ft.update(a[u], val); for(auto v : adj[u]){ if(v != par) change(v, u, val); } } void dfs(ll u, ll par){ if(a[u] != 0){ s[u].insert(a[u]); ft.update(a[u], 1); return; } for(auto v : adj[u]){ if(v != heavy[u] && v != par){ dfs(v, u); change(v, u, -1); if(s[u].size() < s[v].size()) swap(s[u], s[v]); for(auto x : s[v]) s[u].insert(x); } } dfs(heavy[u], u); ll inv = 0; for(auto x : s[u]){ inv = (inv + ft.get(x - 1)); } if(s[heavy[u]].size() > s[u].size()) swap(s[heavy[u]], s[u]); for(auto x : s[heavy[u]]) s[u].insert(x); for(auto v : adj[u]){ if(v != par && v != heavy[u]) change(v, u, 1); } ll cur_sz = s[u].size(); res += min(cur_sz * (cur_sz - 1) / 2 - inv, inv); } void to_thic_cau(){ ll n; cin >> n; input(); ft.init(idx); pre_dfs(1, 0); for(int i = 1; i <= idx;i++) { sort(all(adj[i]), [&](const ll &a, const ll &b){ return sz[a] < sz[b]; }); } dfs(1, 0); cout << res << '\n'; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll tc = 1; //cin >> tc; while(tc--) to_thic_cau(); }
#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...