Submission #39300

#TimeUsernameProblemLanguageResultExecution timeMemory
3930014kgTropical Garden (IOI11_garden)C++11
100 / 100
3007 ms8596 KiB
#include "garden.h" #include "gardenlib.h" #include <algorithm> #include <vector> #define N 150001 #define MP 23 using namespace std; int n, m, start, cycle1_len, cycle2_len; int Sx, Sy, d[N][2], d1[N][2], d2[N][2]; pair<int, int> r[N]; void Push_r(int x, int y) { if (!r[x].first) r[x].first = y; else if (!r[x].second) r[x].second = y; } int dfs(int x, int y, int len) { d[x][y] = len; int nx = y ? r[x].second : r[x].first; int ny = r[nx].second && r[nx].first == x ? 1 : 0; if (d[nx][ny]) { if (d[nx][ny] == 1) return len; else return -1; } return dfs(nx, ny, len + 1); } int dfs_find1(int x, int y) { if (x == start && y == 0) return 0; if (d1[x][y] != 0) return d1[x][y]; int nx = y ? r[x].second : r[x].first; int ny = r[nx].second && r[nx].first == x ? 1 : 0; d1[x][y] = -1, d1[x][y] = dfs_find1(nx, ny); if (d1[x][y] >= 0) d1[x][y]++; return d1[x][y]; } int dfs_find2(int x, int y) { if (x == start && y == 1) return 0; if (d2[x][y] != 0) return d2[x][y]; int nx = y ? r[x].second : r[x].first; int ny = r[nx].second && r[nx].first == x ? 1 : 0; d2[x][y] = -1, d2[x][y] = dfs_find2(nx, ny); if (d2[x][y] >= 0) d2[x][y]++; return d2[x][y]; } void count_routes(int _n, int _m, int _s, int _r[][2], int Q_len, int Q[]) { n = _n, start = _s + 1; for (int i = 0; i < _m; i++) { int x = _r[i][0] + 1, y = _r[i][1] + 1; Push_r(x, y), Push_r(y, x); } cycle1_len = dfs(start, 0, 1); for (int i = 1; i <= n; i++) d[i][0] = d[i][1] = 0; cycle2_len = dfs(start, 1, 1); for (int i = 1; i <= n; i++) d[i][0] = d[i][1] = 0; for (int i = 1; i <= n; i++) { if (d1[i][0] == 0) dfs_find1(i, 0); if (d2[i][0] == 0) dfs_find2(i, 0); if (i == start) d1[i][0] = 0; } for (int i = 0; i < Q_len; i++) { int res = 0; if (Q[i] == 0) { answer(1); continue; } for (int j = 1; j <= n; j++) { if (d1[j][0] == Q[i] || d2[j][0] == Q[i]) res++; else if ((d1[j][0] > 0 || j == start) && cycle1_len > 0 && Q[i] >= d1[j][0] && (Q[i] - d1[j][0]) % cycle1_len == 0) res++; else if (d2[j][0] > 0 && cycle2_len > 0 && Q[i] >= d2[j][0] && (Q[i] - d2[j][0]) % cycle2_len == 0) res++; } answer(res); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...