Submission #1105887

#TimeUsernameProblemLanguageResultExecution timeMemory
1105887trandangquangUntitled (POI11_rot)C++14
63 / 100
162 ms43080 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for(int i = (a); i <= (b); ++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define ii pair <int, int> #define fi first #define se second #define eb emplace_back #define sz(a) (int)(a).size() #define all(a) (a).begin(), (a).end() using namespace std; const int mxN = 5e5+5; const int mxL = 2e5+5; int n, val[mxN], sub[mxN], tin[mxN], tout[mxN], tour[mxN], Time, cur, ans; vector <int> valN[mxN], ch[mxN]; int newNode() { return ++cur; } struct fenwickTree { int f[mxL]; void upd(int id, int val) { for(; id<mxL; id+=id&-id) f[id]+=val; } int get(int id) { int res = 0; for(; id>0; id-=id&-id) res+=f[id]; return res; } } fwt; struct reverseFenwickTree { int f[mxL]; void upd(int id, int val) { for(; id>0; id-=id&-id) f[id]+=val; } int get(int id) { int res = 0; for(; id<mxL; id+=id&-id) res+=f[id]; return res; } } rfwt; void input(int node) { int x; cin >> x; if(x == 0) { int lfN = newNode(); input(lfN); int rtN = newNode(); input(rtN); ch[node].eb(lfN); ch[node].eb(rtN); } else { val[node] = x; } } void pre_dfs(int u) { tin[u] = ++Time; tour[Time] = u; sub[u] = 1; for(int v:ch[u]) { pre_dfs(v); sub[u] += sub[v]; } tout[u] = Time; } void dfs(int u) { int bigCh = -1; for(int v:ch[u]) if(bigCh == -1 || sub[v]>sub[bigCh]) bigCh=v; for(int v:ch[u]) if(v != bigCh) { dfs(v); FOR(i,tin[v],tout[v]){ if(val[tour[i]]) { fwt.upd(val[tour[i]], -1); rfwt.upd(val[tour[i]], -1); } } } if(bigCh != -1) dfs(bigCh); /// main solve int res=0, rres=0; for(int v:ch[u]) if(v != bigCh) { FOR(i,tin[v],tout[v]){ if(val[tour[i]]) { res+=fwt.get(val[tour[i]]-1); rres+=rfwt.get(val[tour[i]]+1); } } FOR(i,tin[v],tout[v]){ if(val[tour[i]]) { fwt.upd(val[tour[i]], 1); rfwt.upd(val[tour[i]], 1); } } } ans += min(res, rres); if(val[u]) { fwt.upd(val[u], 1); rfwt.upd(val[u], 1); } } int main() { if(fopen("test.inp", "r")) { freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } cin.tie(0)->sync_with_stdio(0); cin >> n; cur = 1; input(1); pre_dfs(1); dfs(1); cout << ans; }

Compilation message (stderr)

rot.cpp: In function 'int main()':
rot.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rot.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...