Submission #964751

#TimeUsernameProblemLanguageResultExecution timeMemory
964751PieArmyRegions (IOI09_regions)C++17
2 / 100
2020 ms82400 KiB
typedef long long ll; ll pie(ll army){return (1ll<<army);} #include <bits/stdc++.h> #define fr first #define sc second #define pb push_back #define mid ((left+right)>>1) const ll inf=2000000000000000005; const int sonsuz=2000000005; using namespace std; ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;} int n,sq,R,Q; int pre[25001][450],pre2[450][25001],say[25001],renk[200001],fazlapos[25001],bas[200001],son[200001]; vector<int>child[200001],var[25001],sirali[25001]; int cal(int a,int b){ if(say[b]==0){ return 0; } if(say[b]>sq){ return pre[a][fazlapos[b]]; } if(say[a]>sq){ return pre2[fazlapos[a]][b]; } int sta[say[a]]; int tavan=-1; int apos=0; int ans=0; for(int i=say[b]-1;i>=0;i--){ while(tavan!=-1&&bas[sta[tavan]]>bas[var[b][i]]){ tavan--; } while(apos<say[a]&&son[sirali[a][apos]]>=bas[var[b][i]]){ if(bas[sirali[a][apos]]<=bas[var[b][i]]){ tavan++; sta[tavan]=sirali[a][apos]; } apos++; } ans+=tavan+1; } return ans; } void code(){ cin>>n>>R>>Q; sq=sqrt(n); cin>>renk[1]; int time=0; say[renk[1]]++; for(int &x:fazlapos) x=-1; for(int i=2;i<=n;i++){ int par;cin>>par; child[par].pb(i); cin>>renk[i]; if(say[renk[i]]==sq){ fazlapos[renk[i]]=time; time++; } say[renk[i]]++; } function<int(int,int)>f=[&](int pos,int tur)->int{ int res=0; for(int x:child[pos]){ res+=f(x,tur); } if(renk[pos]==tur)return res+1; pre[renk[pos]][fazlapos[tur]]+=res; return res; }; function<void(int,int,int)>f2=[&](int pos,int tur,int sum)->void{ if(renk[pos]!=tur)pre2[fazlapos[tur]][renk[pos]]+=sum; else sum++; for(int x:child[pos]){ f2(x,tur,sum); } }; for(int i=1;i<=R;i++){ if(fazlapos[i]==-1)continue; f(1,i); //f2(1,i,0); } time=1; function<void(int)>turla=[&](int pos)->void{ if(say[renk[pos]]<=sq){ bas[pos]=time; var[renk[pos]].pb(pos); sirali[renk[pos]].pb(pos); } time++; for(int x:child[pos]){ turla(x); } son[pos]=time-1; }; turla(1); for(int i=1;i<=R;i++){ if(say[i]>sq)continue; sort(sirali[i].begin(),sirali[i].end(),[&](const int &x,const int &y){ if(son[x]==son[y]){ return bas[x]>bas[y]; } return son[x]>son[y]; }); } while(Q--){ int a,b;cin>>a>>b; cout<<cal(a,b)<<endl; } } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);} int t=1; if(!t)cin>>t; while(t--){code();cout<<endl;} return 0; }

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:117:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:117:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...