Submission #1086756

#TimeUsernameProblemLanguageResultExecution timeMemory
1086756asli_bgTropical Garden (IOI11_garden)C++11
0 / 100
28 ms60500 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=150005; const int MAXK=30; #define mid (l+r)/2 #define endl '\n' int n,m,p; vii adj[MAXN]; int suc[MAXN][MAXK][3]; int cik[MAXN][MAXK][3]; int cur[MAXN]; int rt[MAXN]; vi route[MAXN]; 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]]; } 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]]; } } } } 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; 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; 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)); map<int,int> cev; FORE(i,1,n+1){ cur[i]=i; route[i].pb(i); } FORE(i,1,n+1) rt[i]=1; int once=0; FORE(i,1,n+1){ for(auto ell:qq){ auto el=ell; el-=once; if(el==0) continue; FOR(j,MAXK){ if((1<<j)>el) break; if(el&(1<<j)){ int node=cur[i]; cur[i]=suc[node][j][rt[i]]; rt[i]=cik[node][j][rt[i]]; if(cur[i]==i and rt[i]==1){ break; } route[i].pb(cur[i]); } } int sz=route[i].size(); if(route[i][ell%sz]==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...