Submission #1078373

#TimeUsernameProblemLanguageResultExecution timeMemory
1078373dwuyTropical Garden (IOI11_garden)C++14
49 / 100
33 ms14432 KiB
/** - dwuy -       />  フ       |  _  _|       /`ミ _x ノ      /      |     /  ヽ   ?  / ̄|   | | |  | ( ̄ヽ__ヽ_)_)  \二つ **/ #include <bits/stdc++.h> #include "garden.h" #include "gardenlib.h" #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout) #define fi first #define se second #define endl "\n" #define len(s) (int)((s).size()) #define MASK(k)(1LL<<(k)) #define TASK "test" using namespace std; typedef tuple<int, int, int> tpiii; typedef pair<double, double> pdd; typedef pair<int, int> pii; typedef long long ll; const long long OO = 1e18; const int MOD = 1e9 + 7; const int INF = 1e9 + 5e8; const int MX = 150005; int n, m, P; int L1, L2; int d[MX*2][2]; int dis[MX][2]; bool vist[MX][2]; bool f[MX][2]; vector<int> G[MX]; void dfs(int u, int pre){ if(dis[u][pre] != -1) return; if(vist[u][pre]){ dis[u][pre] = INF; return; } vist[u][pre] = 1; if(pre == 0 || G[u].size() == 1){ int v = G[u][0]; int nxt = G[v][0] == u; dfs(v, nxt); dis[u][pre] = dis[v][nxt] + 1; f[u][pre] |= f[v][nxt]; } else{ int v = G[u][1]; int nxt = G[v][0] == u; dfs(v, nxt); dis[u][pre] = dis[v][nxt] + 1; f[u][pre] |= f[v][nxt]; } } void calcL2(){ memset(vist, 0, sizeof vist); int u = P, pre = 0; do{ if(vist[u][pre]){ L2 = INF; break; } L2++; vist[u][pre] = 1; if(pre == 0 || G[u].size() == 1){ int v = G[u][0]; int nxt = G[v][0] == u; u = v, pre = nxt; } else{ int v = G[u][1]; int nxt = G[v][0] == u; u = v, pre = nxt; } } while(u != P); } void calcL1(){ memset(vist, 0, sizeof vist); int u = P, pre = 1; do{ if(vist[u][pre]){ L1 = INF; break; } L1++; vist[u][pre] = 1; if(pre == 0 || G[u].size() == 1){ int v = G[u][0]; int nxt = G[v][0] == u; u = v, pre = nxt; } else{ int v = G[u][1]; int nxt = G[v][0] == u; u = v, pre = nxt; } } while(u != P); } void count_routes(int N, int M, int P, int R[][2], int Q, int QR[]){ n = N; m = M; ::P = ++P; for(int i=0; i<M; i++){ int u = R[i][0] + 1; int v = R[i][1] + 1; G[u].push_back(v); G[v].push_back(u); } memset(dis, -1, sizeof dis); dis[P][0] = dis[P][1] = 0; f[P][1] = 1; for(int i=1; i<=n; i++) dfs(i, 0); calcL2(); calcL1(); set<int> st; for(int i=1; i<=n; i++) if(dis[i][0] < INF){ d[dis[i][0]][f[i][0]]++; st.insert(dis[i][0]); } for(int i=0; i<Q; i++){ int k = QR[i]; int res = 0; for(int x: st){ if(x > k) break; if((k - x)%L1 == 0) res += d[x][1]; if((k - x)%L2 == 0) res += d[x][0]; } answer(res); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...