#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
void dfs(int st, int dep, vector<int>(&g)[], int f[], int t, int n){
f[st]=dep;
for(int i : g[st]){
if(i==t){
f[t]=dep+1;
continue;
}
if(i==st+n||i==st-n){
dfs(i,dep,g,f,t, n);
continue;
}
dfs(i,dep+1,g,f,t, n);
}
}
void count_routes(int n, int m, int t, int edges[][2], int q, int G[])
{
vector<int>g[2*n];
int cn[n];
fill(cn,cn+n,0);
for(int i = 0;i<m;i++){
int u1=edges[i][0];
int v1=edges[i][1];
if(cn[u1]>cn[v1]){
swap(u1,v1);
}
int u2 = u1+n;
int v2 = v1+n;
if(cn[u1]==0&&cn[v1]==0){
g[v2].push_back(u1);
g[u2].push_back(v1);
}
else if(cn[u1]==0&&cn[v1]==1){
g[v1].push_back(u1);
g[u2].push_back(v2);
}
else if(cn[u1]==0&&cn[v1]>1){
g[v1].push_back(u1);
}
else if(cn[u1]==1&&cn[v1]==1){
g[v1].push_back(u2);
g[u1].push_back(v2);
}
else if(cn[u1]==1&&cn[v1]>1){
g[v1].push_back(u2);
}
cn[u1]++;
cn[v1]++;
}
for(int i = 0;i<n;i++){
if(cn[i]==1){
g[i].push_back(i+n);
}
} int f1[2*n];
fill(f1,f1+2*n,-1);
queue<pair<int,int>>qu;
for(int v : g[t]){
qu.push({v,1});
}
while(!qu.empty()){
pair<int,int>p=qu.front();
qu.pop();
assert(f1[p.first]==-1);
f1[p.first]=p.second;
if(p.first==t)
continue;
for(int v : g[p.first]){
if(v==p.first+n||v==p.first-n){
qu.push({v,p.second});
continue;
}
qu.push({v,p.second+1});
}
}
//dfs(t,0,g,f1,t,-1, n);
int f2[2*n];
fill(f2,f2+2*n,-1);
for(int v : g[n+t]){
qu.push({v,1});
}
while(!qu.empty()){
pair<int,int>p=qu.front();
qu.pop();
assert(f2[p.first]==-1);
f2[p.first]=p.second;
if(p.first==n+t)
continue;
for(int v : g[p.first]){
if(v==p.first+n||v==p.first-n){
qu.push({v,p.second});
continue;
}
qu.push({v,p.second+1});
}
}
//dfs(t+n,0,g,f2,t+n,-1, n);
for(int i = 0;i<q;i++){
int ans = 0;
for(int j = 0;j<n;j++){
if(f1[j]!=-1&&f1[j]<=G[i]&&((G[i]==f1[j])||(f1[t]&&f1[t]!=-1&&(G[i]-f1[j])%f1[t]==0))){
ans++;
}
else if(f2[j]!=-1&&f2[j]<=G[i]&&((G[i]==f2[j])||(f2[t+n]&&f2[t]!=-1&&(G[i]-f2[j])%f2[t+n]==0))){
ans++;
}
}
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
