#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
/*
só interessam as duas arestas mais valiosas de um cara
ou vc ta em um ciclo ou vc escoa um ciclo
*/
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int MAXN = 15e4+10, MAXQ = 2e3+10, BIG = 1e9+1;
vector<pii> e[MAXN];
bool inl[MAXN];
int ds[MAXN][2]; // distância até p
bool st[MAXN][2]; // o estado que pega p
bool dfs(int x, int l, int P){
bool cr = 0;
if (e[x].size() > 1 && l == e[x][0].second) cr=1;
if (ds[x][cr] != BIG) return cr;
ds[x][cr] = -1;
auto i = e[x][cr].first;
if (i == P){
ds[x][cr] = 1, st[x][cr] = (e[x][cr].second==e[i][0].second && e[i].size()>1);
return cr;
}
bool is = dfs(i, e[x][cr].second, P);
if (ds[i][is] != -1){
ds[x][cr] = ds[i][is]+1;
st[x][cr] = st[i][is];
}
return cr;
}
void count_routes(int n, int m, int P, int R[][2], int q, int G[]){
for (int i=0;i<n;i++){
e[i].clear();
inl[i]=0, ds[i][0] = ds[i][1] = BIG;
}
for (int i=0;i<m;i++){
int a = R[i][0], b = R[i][1];
if (e[a].size()<2) e[a].emplace_back(b, i);
if (e[b].size()<2) e[b].emplace_back(a, i);
}
for (int i=0;i<n;i++){
if (ds[i][0] == BIG) dfs(i, -1, P);
}
// for (int i=0;i<n;i++) cerr << ds[i][0] << ' ' << ds[i][1] << '\n';
for (int _=0;_<q;_++){
int k = G[_], cr = 0;
for (int i=0;i<n;i++){
int cy = ds[P][st[i][0]], d = ds[i][0];
if (d==-1) continue;
if (cy==-1){
if (d==k) cr++;
}else{
if (d<=k && (k-d)%cy == 0){
cr++;
// cerr << i << " did \n";
}
}
}
answer(cr);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
