제출 #551248

#제출 시각아이디문제언어결과실행 시간메모리
551248Koosha_mv열대 식물원 (Tropical Garden) (IOI11_garden)C++14
100 / 100
2492 ms65332 KiB
#include <bits/stdc++.h> using namespace std; #define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl #define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl #define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define all(v) v.begin(),v.end() #define bit(n,k) (((n)>>(k))&1) #define Add(x,y) x=(x+y)%mod #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first #include "garden.h" #include "gardenlib.h" const int N=1e6+99,inf=1e9+99; int n,m,s,a[N][2],b[N],p[N],vis[N],dist0[N],dist1[N]; vector<int> g[N],adj[N]; void dfs0(int u){ dist0[u]=inf; vis[u]=1; if(u==(s<<1)){ dist0[u]=0; return ; } if(vis[p[u]]==0) dfs0(p[u]); dist0[u]=dist0[p[u]]+1; } void dfs1(int u){ dist1[u]=inf; vis[u]=1; if(u==(s<<1|1)){ dist1[u]=0; return ; } if(vis[p[u]]==0) dfs1(p[u]); dist1[u]=dist1[p[u]]+1; } void count_routes(int _n, int _m, int _s, int R[][2], int Q, int G[]){ n=_n,m=_m,s=_s; f(i,0,m){ int u=R[i][0],v=R[i][1]; if(g[u].size()<2) adj[u].pb(v); if(g[v].size()<2) adj[v].pb(u); } f(i,0,n){ p[i<<1]=(adj[i][0]<<1)+(adj[adj[i][0]][0]==i ? 1 : 0); if(adj[i].size()<2) p[i<<1|1]=p[i<<1]; else{ p[i<<1|1]=(adj[i][1]<<1)+(adj[adj[i][1]][0]==i ? 1 : 0); } } f(i,0,n<<1) if(!vis[i]) dfs0(i); fill(vis,vis+N,0); f(i,0,n<<1) if(!vis[i]) dfs1(i); int u,len0=0,len1=0; fill(vis,vis+N,0); u=s<<1; while(1){ vis[u]=1; len0++; if(vis[p[u]]) break; u=p[u]; } if(p[u]!=(s<<1)) len0=inf; fill(vis,vis+N,0); u=s<<1|1; while(1){ vis[u]=1; len1++; if(vis[p[u]]) break; u=p[u]; } if(p[u]!=(s<<1|1)) len1=inf; f(i,0,Q){ int k=G[i],res=0; f(i,0,n){ //if(i==5){ // eror(dist0[i<<1]); //} if((dist0[i<<1]<=k && (k-dist0[i<<1])%len0==0) || (dist1[i<<1]<=k && (k-dist1[i<<1])%len1==0)){ //eror(i); res++; } } //cout<<"res - "<<res<<endl;; answer(res); } } /* int32_t main(){ ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0); int n,m,s,q; cin>>n>>m>>s>>q; f(i,0,m) cin>>a[i][0]>>a[i][1]; f(i,0,q) cin>>b[i]; count_routes(n,m,s,a,q,b); } */ /* 6 6 0 1 1 2 0 1 0 3 3 4 4 5 1 5 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...