#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int cur, int t, vector<int>& d, int& c, vector<vector<int>>& ed){
for (auto to : ed[cur]){
d[to] = d[cur] + 1;
if (to == t) {
c = d[to] + 1;
continue;
}
dfs(to, t, d, c, ed);
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
const int lg = 32;
vector<vector<int>> ed(n, vector<int>(2, -1));
for (int i = 0; i < m; ++i) {
if (ed[r[i][0]][0] == -1) ed[r[i][0]][0] = r[i][1];
else if (ed[r[i][0]][1] == -1) ed[r[i][0]][1] = r[i][1];
if (ed[r[i][1]][0] == -1) ed[r[i][1]][0] = r[i][0];
else if (ed[r[i][1]][1] == -1) ed[r[i][1]][1] = r[i][0];
}
for (int i = 0; i < n; ++i) {
if (ed[i][1] == -1) ed[i][1] = ed[i][0];
}
vector<vector<int>> gg(2*n);
for (int i = 0; i < n; ++i){
int t1 = ed[i][0];
if (ed[t1][0] == i) gg[t1 + n].push_back(i);
else gg[t1].push_back(i);
int t2 = ed[i][1];
if (ed[t2][0] == i) gg[t2 + n].push_back(i + n);
else gg[t2].push_back(i + n);
}
vector<int> d1(2*n, 2*n + 5); d1[p] = 0;
vector<int> d2(2*n, 2*n + 5); d2[p + n] = 0;
int c1 = 2*n + 5, c2 = 2*n + 5;
dfs(p, p, d1, c1, gg);
dfs(p + n, p + n, d2, c2, gg);
for (int i = 0; i < q; ++i){
int res = 0;
for (int j = 0; j < n; ++j){
if (d1[j] == g[i] || (c1 <= 2*n && g[i] - d1[j] > 0 && (g[i] - d1[j]) % c1 == 0)) res++;
else if (d2[j] == g[i] || (c2 <= 2*n && g[i] - d2[j] > 0 && (g[i] - d2[j]) % c2 == 0)) res++;
}
answer(res);
}
}
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:19:15: warning: unused variable 'lg' [-Wunused-variable]
19 | const int lg = 32;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
