Submission #1259895

#TimeUsernameProblemLanguageResultExecution timeMemory
1259895tormentTropical Garden (IOI11_garden)C++20
0 / 100
3 ms4416 KiB
#include "garden.h" #include <iostream> #include <vector> using namespace std; const int N = 150005; const int LOG = 30; vector<int> g[N], path; int up[LOG][2 * N], tocyc[2 * N], cyc[2 * N], cycsz[2 * N], toP[2][2 * N]; bool vis[2 * N]; int kth(int k, int node){ for(int i = LOG - 1;i >= 0;--i){ if(k >= (1 << i)){ k -= (1 << i); node = up[i][node]; } } return node; } void dfs(int node){ path.push_back(node); vis[node] = 1; if(!vis[up[0][node]]){ dfs(up[0][node]); } else{ if(!cycsz[up[0][node]]){ int sz = 1, cnt = 0; for(int i = (int)path.size() - 1;i >= 0 && path[i] != up[0][node];--i){ sz++; } for(int i = (int)path.size() - 1;i >= 0 && path[i] != up[0][node];--i){ cycsz[path[i]] = sz; cyc[path[i]] = cnt++; } cycsz[up[0][node]] = sz; cyc[up[0][node]] = cnt++; } } if(cycsz[node])return; cycsz[node] = cycsz[up[0][node]]; tocyc[node] = tocyc[up[0][node]] + 1; } void answer(int x); // void answer(int x){ // cout << x << '\n'; // } void count_routes(int n, int m, int p, int r[][2], int q, int k[]){ for(int i = 0;i < m;++i){ int u = r[i][0], v = r[i][1]; g[u].push_back(v); g[v].push_back(u); } for(int i = 0;i < n;++i){ if(g[i].empty())continue; int v = g[i][0]; if(g[v][0] == i){ up[0][i << 1] = ((v << 1) | 1); } else{ up[0][i << 1] = (v << 1); } if(g[i].size() >= 2)v = g[i][1]; else v = g[i][0]; if(g[v][0] == i){ up[0][(i << 1) | 1] = ((v << 1) | 1); } else{ up[0][(i << 1) | 1] = (v << 1); } } for(int i = 1;i < LOG;++i){ for(int j = 0;j < 2 * n;++j){ up[i][j] = up[i - 1][up[i - 1][j]]; } } for(int i = 0;i < 2 * n;++i){ if(!vis[i]){ dfs(i); path.clear(); } } // for(int i = 0;i < 2 * n;++i){ // cout << i << " " << cyc[i] << '\n'; // } for(int i = 0;i < 2 * n;++i){ for(int j = 0;j < 2;++j){ int P = ((p << 1) | j); if(tocyc[P]){ toP[j][i] = max(0, tocyc[i] - tocyc[P]); } else{ int X = kth(tocyc[i], i); toP[j][i] = tocyc[i] + (cyc[X] - cyc[P] + cycsz[P]) % cycsz[P]; } if(kth(toP[j][i], i) != P)toP[j][i] = -1; } } for(int i = 0;i < q;++i){ int K = k[i], cnt = 0; for(int j = 0;j < 2 * n;j += 2){ for(int l = 0;l < 2;++l){ // cout << j / 2 << ": " << toP[l][j] << endl; if(toP[l][j] == -1)continue; int P = ((p << 1) | l); if(tocyc[P]){ cnt += (K == toP[l][j]); } else{ cnt += (K % cycsz[P] == toP[l][j] % cycsz[P]); } } } answer(cnt); } } // int main(){ // ios_base::sync_with_stdio(0); // cin.tie(0); // int n, m, p; // cin >> n >> m >> p; // int r[m][2]; // for(int i = 0;i < m;++i){ // int u, v; // cin >> u >> v; // r[i][0] = u, r[i][1] = v; // } // int q; // cin >> q; // int k[q]; // for(int i = 0;i < q;++i){ // cin >> k[i]; // } // count_routes(n, m, p, r, q, k); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...