Submission #765977

#TimeUsernameProblemLanguageResultExecution timeMemory
765977vjudge1Untitled (POI11_rot)C++17
100 / 100
282 ms44188 KiB
#include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) #define all(a) a.begin() , a.end() #define F first #define S second #define int ll using namespace std; using ll = long long; const int N = 5e5+5 , inf = 2e9 + 7; const ll INF = 1e18 , mod = 1e9+7; int ans[N] , n , mxson[N] , sz[N] , t[N] , m; vector<int> g[N]; void precalc(int v , int pr){ if(v <= n) sz[v] = 1; for(int to : g[v]){ if(to != pr){ precalc(to,v); sz[v] += sz[to]; if(sz[to] > sz[mxson[v]]) mxson[v] = to; } } } void upd(int i, int x){ for(; i <= n; i |= (i + 1)) t[i] += x; } int get(int i){ int res = 0; for(; i > 0; i = (i & (i + 1)) - 1) res += t[i]; return res; } int ob; pair<int,int> calc(int v, int pr){ if(v <= n) { int num = get(v); return {num,ob-num}; } int res = 0 , res1 = 0; for(int to : g[v]){ if(to != pr) { pair<int,int> a = calc(to,v); res += a.F; res1 += a.S; } } return {res,res1}; } void del(int v, int pr){ if(v <= n) upd(v,-1); for(int to : g[v]) if(to != pr) del(to,v); } void add(int v, int pr){ if(v <= n) upd(v,1); for(int to : g[v]) if(to != pr) add(to,v); } void dfs(int v , int pr){ for(int to : g[v]){ if(to != pr && to != mxson[v]){ dfs(to,v); del(to,v); } } if(mxson[v]) { dfs(mxson[v],v); ans[v] += ans[mxson[v]]; } int res = 0 , res1 = 0; for(int to : g[v]){ ob = get(n); if(to != pr && to != mxson[v]) { pair<int,int> b = calc(to,v); res += b.F; res1 += b.S; add(to,v); ans[v] += ans[to]; } } if(v <= n) upd(v,1); else ans[v] += min(res,res1); } int NUM; void go(int v){ int x; cin >> x; if(x == 0){ int to = ++NUM; g[v].push_back(to); g[to].push_back(v); go(to); } else { g[v].push_back(x); g[x].push_back(v); } cin >> x; if(x == 0){ int to = ++NUM; g[v].push_back(to); g[to].push_back(v); go(to); } else { g[v].push_back(x); g[x].push_back(v); } } void solve(){ cin >> n; NUM = n+1; int a; cin >> a; go(n+1); precalc(n+1,0); dfs(n+1,0); cout << ans[n+1] << "\n"; } /* */ signed main(){ ios; solve(); return 0; }
#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...