Submission #548584

#TimeUsernameProblemLanguageResultExecution timeMemory
548584LoboTropical Garden (IOI11_garden)C++17
69 / 100
2635 ms33108 KiB
#include "garden.h" #include "gardenlib.h" #include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() const int maxn = 4e5+10; int n, mark[maxn], p[maxn], ordc[maxn], nx[maxn], disp[maxn], szc[maxn], tin[maxn], timer; vector<pair<int,int>> g[maxn]; void dfsc(int v, int ini) { p[v] = v; disp[v] = 0; if(nx[v] == ini) { szc[mark[v]] = ordc[v]+1; return; } ordc[nx[v]] = ordc[v]+1; dfsc(nx[v],ini); } void dfs(int v, int cur) { tin[v] = ++timer; mark[v] = cur; if(mark[nx[v]] == cur) { //temos um ciclo ordc[nx[v]] = 0; dfsc(nx[v],nx[v]); return; } else if(mark[nx[v]] == -1){ dfs(nx[v],cur); } if(p[v] == -1) { disp[v] = disp[nx[v]]+1; p[v] = p[nx[v]]; } } void count_routes(int32_t N, int32_t M, int32_t P, int32_t R[][2], int32_t Q, int32_t G[]) { n = N; for(int i = 0; i < M; i++) { g[R[i][0]].pb(mp(i,R[i][1])); g[R[i][1]].pb(mp(i,R[i][0])); } for(int i = 0; i < 2*n; i++) { nx[i] = i; } for(int i = 0; i < n; i++) { sort(all(g[i])); } for(int i = 0; i < n; i++) { nx[i] = g[i][0].sc; if(g[nx[i]][0].sc == i) nx[i]+= n; if(g[i].size() == 1) nx[i+n] = g[i][0].sc; else nx[i+n] = g[i][1].sc; if(g[nx[i+n]][0].sc == i) nx[i+n]+= n; } for(int i = 0; i < 2*n; i++) { p[i] = -1; mark[i] = -1; ordc[i] = -1; } for(int i = 0; i < 2*n; i++) { if(mark[i] == -1) { dfs(i,i); } } for(int j = 0; j < Q; j++) { int ans = 0; for(int i = 0; i < n; i++) { int k = G[j]; int v = i; if(P != p[P]) { if(p[v] == p[P] && k == tin[P]-tin[v] && k == disp[v]-disp[P]) ans++; } else { if(mark[p[v]] == mark[P] && k >= disp[v] && (ordc[p[v]]+k-disp[v])%szc[mark[p[v]]] == ordc[P]) ans++; //vai k pra frente de } P+= n; if(P != p[P]) { if(p[v] == p[P] && k == tin[P]-tin[v] && k == disp[v]-disp[P]) ans++; } else { if(mark[p[v]] == mark[P] && k >= disp[v] && (ordc[p[v]]+k-disp[v])%szc[mark[p[v]]] == ordc[P]) ans++; //vai k pra frente de } P-= n; } answer(ans); // cout << ans << endl; } } // int32_t main() { // ios::sync_with_stdio(false); cin.tie(0); // freopen("in.in", "r", stdin); // // freopen("out.out", "w", stdout); // int32_t N, M, P; // cin >> N >> M >> P; // int32_t R[M][2]; // for(int i = 0; i < M; i++) { // cin >> R[i][0] >> R[i][1]; // } // int32_t Q; cin >> Q; // int32_t G[Q]; // for(int i = 0; i < Q; i++) { // cin >> G[i]; // } // count_routes(N,M,P,R,Q,G); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...