제출 #99224

#제출 시각아이디문제언어결과실행 시간메모리
99224eriksuenderhauf열대 식물원 (Tropical Garden) (IOI11_garden)C++11
100 / 100
3741 ms27408 KiB
#pragma GCC optimize("O3") #include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> #define pri(n) printf("%d\n", (n)) #define pb push_back using namespace std; const int MAXN = 3e5 + 5; int nx[31][MAXN]; int dist[MAXN][2], vis[MAXN]; vector<int> adj[MAXN]; void dfs(int u, int fr, int d, int tmp) { if (vis[u] && u != tmp) return; dist[u][fr] = d; if (u == tmp && d != 0) return; if (vis[u]) return; vis[u] = 1; for (int v: adj[u]) dfs(v, fr, d + 1, tmp); } void count_routes(int n, int m, int p, int r[][2], int q, int g[]) { for (int i = 0; i < 2*n; i++) nx[0][i] = -1; for (int i = 0; i < m; i++) { int u = r[i][0], v = r[i][1]; int f1 = 0, f2 = 0, f3 = 0, f4 = 0; if (nx[0][2*u] == -1) f1 = 1; if (nx[0][2*v] == -1) f2 = 1; if (nx[0][2*u+1] == -1) f3 = 1; if (nx[0][2*v+1] == -1) f4 = 1; if (f1) { if (f2) nx[0][2*u] = 2*v+1, adj[2*v+1].pb(2*u); else nx[0][2*u] = 2*v, adj[2*v].pb(2*u); } else if (f3) { if (f2) nx[0][2*u+1] = 2*v+1, adj[2*v+1].pb(2*u+1); else nx[0][2*u+1] = 2*v, adj[2*v].pb(2*u+1); } if (f2) { if (f1) nx[0][2*v] = 2*u+1, adj[2*u+1].pb(2*v); else nx[0][2*v] = 2*u, adj[2*u].pb(2*v); } else if (f4) { if (f1) nx[0][2*v+1] = 2*u+1, adj[2*u+1].pb(2*v+1); else nx[0][2*v+1] = 2*u, adj[2*u].pb(2*v+1); } } for (int i = 1; i < 2*n; i += 2) if (nx[0][i] == -1) nx[0][i] = nx[0][i - 1], adj[nx[0][i - 1]].pb(i); dfs(2*p,0,0,2*p); memset(vis, 0, sizeof vis); dfs(2*p+1,1,0,2*p+1); for (int i = 0; i < q; i++) { int ans = 0; for (int j = 0; j < n; j++) { if (dist[2*j][0] == 0 && dist[2*j][1] == 0) continue; if (dist[2*j][0] == g[i] || dist[2*j][1] == g[i]) { ans++; continue; } if (dist[2*p][0] != 0 && (g[i] - dist[2*j][0]) % dist[2*p][0] == 0 && g[i] > dist[2*j][0] && dist[2*j][0] != 0) ans++; else if (dist[2*p+1][1] != 0 && (g[i] - dist[2*j][1]) % dist[2*p+1][1] == 0 && g[i] > dist[2*j][1] && dist[2*j][1] != 0) ans++; } answer(ans); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...