Submission #106825

#TimeUsernameProblemLanguageResultExecution timeMemory
106825luciocfTropical Garden (IOI11_garden)C++14
100 / 100
3910 ms33256 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; bool comp[maxn]; bool mark[maxn], mark2[maxn], inCycle[maxn]; vector<int> rev[maxn]; void makeGraph(int N) { for (int i = 0; i < N; i++) { int u = grafo[0][i], v = grafo[1][i]; 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, int cc) { mark2[u] = true, comp[u] = cc; for (auto v: rev[u]) { if (mark2[v]) continue; nivel[v] = nivel[u]+1; getNivel(v, cc); } } 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]) || (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 = dist[q][i]; 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); for (int i = 0; i < 2*N; i++) if (pai[i] != -1) rev[pai[i]].push_back(i); int r = getRoot(P); getNivel(r, 1); if (!mark2[P+N]) { r = getRoot(P+N); getNivel(r, 0); } int ini1 = -1, fim1 = -1; int ini2 = -1, fim2 = -1; for (int i = 0; i < 2*N; i++) { if (comp[i] == comp[P] && nivel[pai[i]] > nivel[i]) ini1 = pai[i], fim1 = i, sz1 = nivel[pai[i]]-nivel[i]+1; if (comp[i] == comp[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 (comp[i] == comp[P] && check(i, P, K, 1)) ans++; else if (comp[i] == comp[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...