#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
vector<pair<int, int> > g[MAXN];
vector<pair<int, int> > edges;
bool vis[MAXN * 2];
int parent[20][MAXN * 2];
void dfs(int node, int par, int idx) {
//cout << "node = " << node << "\n";
vis[idx] = true;
for(int i = 0; i < g[node].size(); i++) {
if(g[node][i].first != par || g[node].size() == 1) {
//cout << node << "->" << par << "\n";
parent[0][idx] = g[node][i].second;
if(vis[g[node][i].second]) return;
dfs(g[node][i].first, node, g[node][i].second);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
int cnt = 0;
for(int i = 0; i < M; i++) {
if(g[R[i][0]].size() < 2) {
g[R[i][0]].push_back(make_pair(R[i][1], cnt++));
edges.push_back(make_pair(R[i][0], R[i][1]));
}
if(g[R[i][1]].size() < 2) {
g[R[i][1]].push_back(make_pair(R[i][0], cnt++));
edges.push_back(make_pair(R[i][1], R[i][0]));
}
}
/*for(int i = 0; i < N; i++) {
cout << "Source: " << i << "\n";
for(int j = 0; j < g[i].size(); j++) {
cout << g[i][j].first << ", " << g[i][j].second << "\n";
}
cout << "\n\n";
}*/
for(int i = 0; i < cnt; i++) {
if(!vis[i]) {
dfs(edges[i].second, edges[i].first, i);
}
}
/*cout << "Immediate parents\n";
for(int i = 0; i < cnt; i++) {
cout << edges[i].first << "->" << edges[i].second << ", par = " << parent[0][i] << "\n";
// cout << parent[0][i] << " ";
}
cout << "\n";*/
for(int i = 1; i < 20; i++) {
for(int j = 0; j < cnt; j++) {
assert(parent[i - 1][j] >= 0 && parent[i - 1][j] < cnt);
parent[i][j] = parent[i - 1][parent[i - 1][j]];
}
}
for(int i = 0; i < Q; i++) {
int ans = 0;
G[i]--;
for(int j = 0; j < cnt; j++) {
int diff = G[i], idx = j;
for(int k = 19; k >= 0; k--) {
if(diff >= (1 << k)) {
diff -= (1 << k);
idx = parent[k][idx];
}
}
if(edges[idx].second == P) {
ans++;
}
}
answer(ans);
}
}
Compilation message
garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int i = 0; i < g[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
5316 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
5316 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
5316 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |