Submission #744657

#TimeUsernameProblemLanguageResultExecution timeMemory
744657CSQ31Tropical Garden (IOI11_garden)C++17
0 / 100
10 ms19284 KiB
#include "garden.h" #include <bits/stdc++.h> #include "gardenlib.h" using namespace std; const int MAXN = 4e5; vector<int>g[MAXN],adj[MAXN]; int jump[MAXN],cycle[MAXN],col[MAXN],dist[MAXN],vis[MAXN],ans[MAXN]; void dfs(int v){ col[v] = 1; if(col[jump[v]] ==1)cycle[v] = 1; else if(!col[jump[v]])dfs(jump[v]); col[v] = 2; } void dfs2(int v){ vis[v] = 1; for(int x:adj[v]){ if(!vis[x]){ dist[x] = dist[v]+1; dfs2(x); } } } void count_routes(int n, int m, int p, int r[][2], int q, int G[]) { for(int i=0;i<m;i++){ g[r[i][0]].push_back(r[i][1]); g[r[i][1]].push_back(r[i][0]); } for(int i=0;i<n;i++){ //2*i -> most beautiful route wasnt taken last turn //2*i+1 ->most beautiful route was taken int v = g[i][0]; if(g[v][0] != i)jump[2*i] = 2*v; else jump[2*i] = 2*v+1; int s = g[i].size(); if(s > 1)v = g[i][1]; if(g[v][0] != i)jump[2*i+1] = 2*v; else jump[2*i+1] = 2*v+1; } for(int i=0;i<2*n;i++){ if(!col[i])dfs(i); if(cycle[i]){ int v = jump[i]; while(!cycle[v]){ cycle[v] = 1; v = jump[v]; } } adj[jump[i]].push_back(i); dist[i] = 1e9; } //for(int i=0;i<2*n;i++)cout<<cycle[i]<<" "; //cout<<'\n'; //for(int i=0;i<2*n;i++)cout<<jump[i]<<" "; cout<<'\n'; dist[2*p] = 0; dfs2(2*p); if(!cycle[2*p]){ vector<int>cnt(n+1,0); for(int i=0;i<n;i++){ if(dist[2*i] != 1e9)cnt[dist[2*i]]++; } for(int i=0;i<q;i++){ if(G[i]<=n)ans[i]+=cnt[G[i]]; } }else{ int len = 0; int v = 2*p; while(cycle[v]==1){ len++; v = jump[v]; cycle[v]++; } vector<vector<int>>mod(n); for(int i=0;i<n;i++){ if(dist[2*i] != 1e9){ int x = dist[2*i]; mod[x%len].push_back(x); } } for(int i=0;i<len;i++)sort(mod[i].begin(),mod[i].end()); for(int i=0;i<q;i++){ int rem = G[i]%len; if(mod[rem].empty())continue; int pt = upper_bound(mod[rem].begin(),mod[rem].end(),G[i]) - mod[rem].begin(); ans[i]+=pt; } } for(int i=0;i<2*n;i++)dist[i] = 1e9; dist[2*p+1] = 0; dfs2(2*p+1); if(!cycle[2*p+1]){ vector<int>cnt(n+1,0); for(int i=0;i<n;i++){ if(dist[2*i] != 1e9)cnt[dist[2*i]]++; } for(int i=0;i<q;i++){ if(G[i]<=n)ans[i]+=cnt[G[i]]; } }else{ int len = 0; int v = 2*p+1; while(cycle[v]){ len++; cycle[v] = 0; v = jump[v]; } //cout<<len<<'\n'; //for(int i=0;i<n;i++)cout<<dist[2*i]<<" "; //cout<<'\n'; vector<vector<int>>mod(len); for(int i=0;i<n;i++){ if(dist[2*i] != 1e9){ int x = dist[2*i]; mod[x%len].push_back(x); } } for(int i=0;i<len;i++)sort(mod[i].begin(),mod[i].end()); for(int i=0;i<q;i++){ int rem = G[i]%len; if(mod[rem].empty())continue; int pt = upper_bound(mod[rem].begin(),mod[rem].end(),G[i]) - mod[rem].begin(); ans[i]+=pt; } } for(int i=0;i<q;i++)answer(ans[i]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...