#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MX = 150011;
vector<int> adj[MX * 2], g[MX * 2];
int need[MX * 2][2];
void connect(int u , int v, int N) {
if (adj[u][0] == v || adj[u][0] == v - N)
u = u + N;
g[u].push_back(v);
}
void dfs(int u , int cost, int it) {
if (need[u][it] != -1)
return;
if (cost)
need[u][it] = cost;
for (int i = 0; i < g[u].size(); ++i) {
dfs(g[u][i], cost + 1, it);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
memset(need, -1, sizeof need);
for (int i = 0; i < M; ++i) {
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
for (int i = 0; i < N; ++i) {
while (adj[i].size() > 2)
adj[i].pop_back();
if (adj[i].size())
connect(adj[i][0], i, N);
if (adj[i].size()) {
if (adj[i].size() == 2) {
connect(adj[i][1], i + N, N);
} else {
connect(adj[i][0], i + N, N);
}
}
}
dfs(P, 0, 0);
dfs(P + N, 0, 1);
for (int i = 0; i < N; ++i){
printf("%d = %d %d\n",i,need[i][0],need[i][1] );
}
for (int k = 0 ; k < Q ; k++) {
int res = 0;
for (int i = 0; i < N; ++i) {
for (int it = 0 ; it < 2 ; it++) {
if(need[i][it] == -1)
continue;
int rem = G[k];
if(rem < need[i][it])
continue;
rem -= need[i][it];
if(rem == 0 || (need[P+it*N][it] != -1 && rem%need[P+it*N][it] == 0)){
res++;
break;
}
}
}
answer(res);
}
}
Compilation message
garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[u].size(); ++i) {
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
16916 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
16916 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
16916 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |