Submission #519509

#TimeUsernameProblemLanguageResultExecution timeMemory
519509AdamGSTropical Garden (IOI11_garden)C++17
100 / 100
97 ms19244 KiB
#include "garden.h" #include "gardenlib.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=3e5+7, INF=1e9+7; int nxt[LIM], odl[LIM], cnt[LIM], ile[LIM][2], ans[LIM][2], cykl[2], n; vector<int>V[LIM]; void sortuj() { int ma=0, ilei=0; rep(i, n) { if(odl[i]==INF) ++ilei; else ma=max(ma, odl[i]); } rep(i, n) if(odl[i]<INF) ++cnt[odl[i]]; int l=0; for(int i=0; cnt[ma]; ++i) { while(!cnt[l]) ++l; odl[i]=l; --cnt[l]; } for(int i=n-1; ilei; --i, --ilei) odl[i]=INF; } void solve(int x, int r) { cykl[r]=INF; rep(i, 2*n) odl[i]=INF; odl[x]=0; queue<int>q; q.push(x); while(!q.empty()) { int p=q.front(); q.pop(); for(auto i : V[p]) if(odl[i]>odl[p]+1) { odl[i]=odl[p]+1; q.push(i); } for(auto i : V[p]) if(i==x) cykl[r]=odl[p]+1; } sortuj(); int l=0; rep(i, LIM) { int s=l; while(s<n && odl[s]==i) { ++ans[i][r]; ++s; } if(cykl[r]<INF) { ans[i][r]+=ile[i%cykl[r]][r]; } while(l<n && odl[l]==i) { ++ile[i%cykl[r]][r]; ++l; } } } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { n=N; rep(i, 2*n) nxt[i]=-1; rep(i, M) { int p1=R[i][1], p2=R[i][0]; if(nxt[R[i][1]]==-1) p1+=n; if(nxt[R[i][0]]==-1) p2+=n; if(nxt[R[i][0]]==-1) nxt[R[i][0]]=p1; else if(nxt[R[i][0]+n]==-1) nxt[R[i][0]+n]=p1; if(nxt[R[i][1]]==-1) nxt[R[i][1]]=p2; else if(nxt[R[i][1]+n]==-1) nxt[R[i][1]+n]=p2; } rep(i, n) if(nxt[i]!=-1 && nxt[n+i]==-1) nxt[n+i]=nxt[i]; rep(i, 2*n) if(nxt[i]!=-1) V[nxt[i]].pb(i); solve(P, 0); solve(P+n, 1); rep(i, Q) { if(G[i]<LIM) answer(ans[G[i]][0]+ans[G[i]][1]); else { int x=0; if(cykl[0]<INF) x+=ile[G[i]%cykl[0]][0]; if(cykl[1]<INF) x+=ile[G[i]%cykl[1]][1]; answer(x); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...