제출 #106803

#제출 시각아이디문제언어결과실행 시간메모리
106803luciocf열대 식물원 (Tropical Garden) (IOI11_garden)C++14
69 / 100
5033 ms28172 KiB
#include <bits/stdc++.h> #include "garden.h" #include "gardenlib.h" using namespace std; const int maxn = 3e5+10; typedef pair<int, int> pii; int grafo[2][maxn]; int pai[maxn], nivel[maxn], dist[2][maxn]; int sz1, sz2; int pai_uf[maxn], peso_uf[maxn]; bool mark[maxn], mark2[maxn], inCycle[maxn]; vector<int> rev[maxn]; void init(int N) { for (int i = 0; i < N; i++) pai_uf[i] = i, peso_uf[i] = 1; } int Find(int x) { if (pai_uf[x] == x) return x; return pai_uf[x] = Find(pai_uf[x]); } void Join(int x, int y) { x = Find(x), y = Find(y); if (x == y) return; if (peso_uf[x] < peso_uf[y]) swap(x, y); pai_uf[y] = x, peso_uf[x] += peso_uf[y]; } void makeGraph(int N) { for (int i = 0; i < N; i++) { int u = grafo[0][i], v = grafo[1][i]; if (u == -1 && v == -1) continue; if (v == -1) { if (grafo[0][u] == i) pai[i] = u+N; else pai[i] = u; continue; } if (grafo[0][u] == i && grafo[1][u] != -1) pai[i] = u+N; else pai[i] = u; if (grafo[0][v] == i && grafo[1][v] != -1) pai[i+N] = v+N; else pai[i+N] = v; } } int getRoot(int u) { mark[u] = true; if (mark[pai[u]]) return u; return getRoot(pai[u]); } void getNivel(int u) { mark2[u] = true; for (auto v: rev[u]) { if (mark2[v]) continue; nivel[v] = nivel[u]+1; getNivel(v); } } void getCycle(int u, int fim) { inCycle[u] = true; if (u != fim) getCycle(pai[u], fim); } void bfs(int u, bool q) { memset(mark, 0, sizeof mark); queue<int> fila; fila.push(u), dist[q][u] = 0; while (!fila.empty()) { int u = fila.front(); fila.pop(); for (auto v: rev[u]) { if (!mark[v]) { fila.push(v); mark[v] = 1; dist[q][v] = dist[q][u]+1; } } } } bool check(int i, int P, int K, bool q) { int sz = (q ? sz1 : sz2); if (inCycle[P] && inCycle[i]) { int d = (nivel[i] >= nivel[P] ? nivel[i]-nivel[P] : sz-(nivel[P]-nivel[i])); if (d <= K && K%sz == d%sz) return true; } else if (inCycle[P] && !inCycle[i]) { int d = dist[q][i]; if (d <= K && K%sz == d%sz) return true; } else if (dist[q][i] != -1 && !inCycle[P] && !inCycle[i]) { int d = nivel[i]-nivel[P]; if (d == K) return true; } return false; } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { memset(pai, -1, sizeof pai); memset(grafo, -1, sizeof grafo); memset(dist, -1, sizeof dist); for (int i = 0; i < M; i++) { int u = R[i][0], v = R[i][1]; if (grafo[0][u] == -1) grafo[0][u] = v; else if (grafo[1][u] == -1) grafo[1][u] = v; if (grafo[0][v] == -1) grafo[0][v] = u; else if (grafo[1][v] == -1) grafo[1][v] = u; } makeGraph(N); init(2*N); for (int i = 0; i < 2*N; i++) if (pai[i] != -1) rev[pai[i]].push_back(i), Join(i, pai[i]); for (int i = 0; i < 2*N; i++) { if (!mark2[i] && pai[i] != -1) { int R = getRoot(i); getNivel(R); } } int ini1=-1, fim1=-1; int ini2=-1, fim2=-1; for (int i = 0; i < 2*N; i++) { if (Find(i) == Find(P) && nivel[pai[i]] > nivel[i]) ini1 = pai[i], fim1 = i, sz1 = nivel[pai[i]]-nivel[i]+1; if (Find(i) == Find(P+N) && nivel[pai[i]] > nivel[i]) ini2 = pai[i], fim2 = i, sz2 = nivel[pai[i]]-nivel[i]+1; } if (ini1 != -1) getCycle(ini1, fim1); if (ini2 != -1) getCycle(ini2, fim2); bfs(P, 1); bfs(P+N, 0); for (int q = 0; q < Q; q++) { int K = G[q], ans = 0; for (int i = 0; i < N; i++) { if (Find(i) == Find(P) && check(i, P, K, 1)) ans++; else if (Find(i) == Find(P+N) && check(i, P+N, K, 0)) ans++; } answer(ans); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...