Submission #1020675

#TimeUsernameProblemLanguageResultExecution timeMemory
1020675cnn008Untitled (POI11_rot)C++17
0 / 100
54 ms23644 KiB
#include "bits/stdc++.h" using namespace std; #ifdef N_N_C #include "debug.h" #else #define cebug(...) "Arya" #endif #define ll long long const int N=2e5+5; const int mod=1e9+7; int n,node=1,a[N],sz[N],cur,cur2,leaf[N]; ll ans[N]; vector <int> g[N]; struct BIT{ #define gb(x) (x&(-x)) int n; vector <int> bit; void init(int _n){ bit.resize(_n,0); n=_n; } void update(int pos, int val){ int i=pos; for (; i<n; i+=gb(i)) bit[i]+=val; } int get(int pos){ int ans=0,i=pos; for (; i>=1; i-=gb(i)) ans+=bit[i]; return ans; } }fw; struct BIT2{ #define gb(x) (x&(-x)) int n; vector <int> bit; void init(int _n){ bit.resize(_n,0); n=_n; } void update(int pos, int val){ int i=pos; for (; i; i-=gb(i)) bit[i]+=val; } int get(int pos){ int ans=0,i=pos; for (; i<n; i+=gb(i)) ans+=bit[i]; return ans; } }fw2; void input(){ int x; cin>>x; a[node]=x; if(x) return; int nw=node; g[nw].push_back(++node); input(); g[nw].push_back(++node); input(); } void pre_dfs(int u){ if(a[u]) leaf[u]=1; sz[u]=1; for(auto v:g[u]){ pre_dfs(v); sz[u]+=sz[v]; leaf[u]+=leaf[v]; } } void add(int u){ if(a[u]) cur+=fw.get(a[u]-1),cur2+=fw2.get(a[u]+1); for(auto v:g[u]) add(v); } void del(int u){ if(a[u]) fw.update(a[u],-1),fw2.update(a[u],-1); for(auto v:g[u]) del(v); } void upd(int u){ if(a[u]) fw.update(a[u],1),fw2.update(a[u],1); for(auto v:g[u]) upd(v); } void dfs(int u){ if(a[u]){ fw.update(a[u],1); fw2.update(a[u],1); return; } int big=0,small=0; cur=0; cur2=0; for(auto v:g[u]) if(sz[v]>sz[big]) big=v; for(auto v:g[u]){ if(v!=big){ dfs(v); del(v); } } assert(big); dfs(big); for(auto v:g[u]) if(v!=big) add(v),upd(v),small=v; assert(small); ans[u]=ans[small]+ans[big]+min(cur,cur2); cebug(u,cur,cur2); //cout << u << " " << ans[u] << " " << a[big] << " " << a[small] << "\n"; } void sol(){ fw.init(N); fw2.init(N); cin>>n; input(); pre_dfs(1); dfs(1); cout<<ans[1]; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen(".inp", "r", stdin); // freopen(".out", "w", stdout); int tt=1; //cin>>tt; while(tt--){ sol(); } cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; return 0; }

Compilation message (stderr)

rot.cpp: In function 'void dfs(int)':
rot.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define cebug(...) "Arya"
      |                    ^~~~~~
rot.cpp:107:2: note: in expansion of macro 'cebug'
  107 |  cebug(u,cur,cur2);
      |  ^~~~~
#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...