제출 #36270

#제출 시각아이디문제언어결과실행 시간메모리
36270funcsr열대 식물원 (Tropical Garden) (IOI11_garden)C++14
100 / 100
234 ms66792 KiB
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include "garden.h" #include "gardenlib.h" using namespace std; #define INF 1145141919 #define rep(i, n) for (int i=0; i<(n); i++) #define _1 first #define _2 second #define all(x) x.begin(), x.end() #define pb push_back typedef pair<int, int> P; int N, M, T, Q; vector<P> G[150000]; vector<int> G2[150000*2]; int best[150000]; int F[30][150000*2]; int A[2000]; int D[150000*2]; int C[2][150000*2]; inline int fg(P p) { int x = p._2, e = p._1; if (best[x] == e) return x+N; else return x; } inline int go(int x, int s) { for (int k=29; k>=0; k--) if ((s>>k)&1) x = F[k][x]; return x; } int bfs(int s) { queue<int> q; rep(i, 2*N) D[i] = INF; D[s] = 0; q.push(s); int ret = INF; while (!q.empty()) { int x = q.front(); q.pop(); for (int t : G2[x]) { if (t == s) ret = min(ret, D[x]+1); if (D[t] > D[x]+1) { D[t] = D[x]+1; q.push(t); } } } return ret; } void count_routes(int n, int m, int p, int edges[][2], int q, int g[]) { N = n, M = m, T = p, Q = q; rep(i, N) G[i].clear(); rep(i, M) { G[edges[i][0]].pb(P(i, edges[i][1])); G[edges[i][1]].pb(P(i, edges[i][0])); } rep(i, N) best[i] = G[i][0]._1; rep(i, N) { F[0][i] = fg(G[i][0]); F[0][i+N] = fg((G[i].size()>=2)? G[i][1] : G[i][0]); } rep(i, 2*N) G2[i].clear(); rep(i, 2*N) G2[F[0][i]].pb(i); rep(k, 29) rep(i, 2*N) F[k+1][i] = F[k][F[k][i]]; vector<int> S[2]; int r[2]; r[0] = bfs(T ); rep(i, N) S[0].pb(D[i]); sort(all(S[0]), greater<int>()); r[1] = bfs(T+N); rep(i, N) S[1].pb(D[i]); sort(all(S[1]), greater<int>()); rep(i, 2) rep(t, 2*N) C[i][t] = 0; vector<P> qs; rep(i, Q) qs.pb(P(g[i], i)); sort(all(qs)); rep(_, Q) { int k = qs[_]._1, q = qs[_]._2; int ctr = 0; rep(i, 2) { while (!S[i].empty() && S[i].back() <= k) { int t = S[i].back(); if (r[i] != INF) C[i][t%r[i]]++; else if (t == k) ctr++; S[i].pop_back(); } } rep(i, 2) if (r[i] != INF) ctr += C[i][k%r[i]]; A[q] = ctr; } rep(i, Q) answer(A[i]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...