Submission #1086736

#TimeUsernameProblemLanguageResultExecution timeMemory
1086736asli_bgTropical Garden (IOI11_garden)C++11
69 / 100
191 ms195920 KiB
#include<bits/stdc++.h> using namespace std; #include "garden.h" #include "gardenlib.h" //#define int long long #define fi first #define se second #define all(x) x.begin(),x.end() #define pb push_back typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vii; typedef vector<bool> vb; #define sp <<' '<< #define FOR(i,a) for(int i=0;i<(a);i++) #define FORE(i,a,b) for(int i=(a);i<(b);i++) #define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;} #define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;} #define DEBUG(X) { cout << #X << " = " << (X) << endl; } #define carp(x,y) (((x)%mod)*((y)%mod))%mod #define topla(x,y) (((x)%mod)+((y)%mod))%mod const int MAXN=2e5+4; const int MAXK=31; #define mid (l+r)/2 #define endl '\n' int n,m,p; vii adj[MAXN]; int suc[MAXN][MAXK][3]; int gir[MAXN][MAXK][3]; int cik[MAXN][MAXK][3]; void calc(){ FORE(k,1,MAXK){ FORE(nd,1,n+1){ if(suc[nd][k-1][1]!=-1){ //1.routeu izleyerek k-1 adım gidiliyorsa int bir=suc[nd][k-1][1]; suc[nd][k][1]=suc[bir][k-1][cik[nd][k-1][1]];//min edge i kullan da gel cik[nd][k][1]=cik[bir][k-1][cik[nd][k-1][1]]; gir[nd][k][1]=2; } if(suc[nd][k-1][2]!=-1){ int bir=suc[nd][k-1][2]; suc[nd][k][2]=suc[bir][k-1][cik[nd][k-1][2]];//min edge i kullan da gel cik[nd][k][2]=cik[bir][k-1][cik[nd][k-1][2]]; gir[nd][k][2]=1; } } } } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { n=N; m=M; p=P; p++; memset(suc, -1, sizeof suc); FORE(i,1,m+1){ int from=R[i-1][0]; int to=R[i-1][1]; from++;to++; adj[from].pb({i-1,to}); adj[to].pb({i-1,from}); } FORE(i,1,n+1){ sort(all(adj[i])); while(adj[i].size()>2) adj[i].pop_back(); if(adj[i].size()>=1){ int kom=adj[i][0].se; //1.routu izle suc[i][0][1]=kom; gir[i][0][1]=2; // maxla gir if(adj[kom][0].se==i and adj[kom].size()>1){ cik[i][0][1]=2; //successor i'nin hangi nodeundan devam edicem } else{ cik[i][0][1]=1; } } if(adj[i].size()>=2){ //2.bir route varsa //2.routu izle int kom=adj[i][1].se; suc[i][0][2]=kom; gir[i][0][2]=1; //minle gir if(adj[kom][0].se==i and adj[kom].size()>1){ cik[i][0][2]=2; } else{ cik[i][0][2]=1; } } } //calculate successor of each node calc(); int q=Q; vi qq, cc; FOR(i,q){ int deg=G[i]; qq.pb(deg); cc.pb(deg); } sort(all(qq)); vi cur(n+1); map<int,int> cev; FORE(i,1,n+1) cur[i]=i; int once=0; vi rt(n+1,1); for(auto ell:qq){ int el=ell; el-=once; FOR(i,MAXK){ if(el&(1<<i)){ FORE(nd,1,n+1){ if(cur[nd]==-1) continue; int node=cur[nd]; cur[nd]=suc[node][i][rt[nd]]; rt[nd]=cik[node][i][rt[nd]]; } } /*FORE(nd,1,n+1){ DEBUG(nd); DEBUG(cur[nd]); } cout<<endl;*/ } FORE(nd,1,n+1){ if(cur[nd]==p) cev[ell]++; } once+=el; } for(auto el:cc){ answer(cev[el]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...