#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
int d[300005],a,k,n,m,q,p,c[300005],d2[300005],v1[300005],sz,sz1,sz2,st,fx[300005],ch,res[2005];
vector<pair<int,int> >v[300005];
vector<int>rv[300005];
set<int>s;
void cch(int x,int dis,int st){
for(int i=0;i<rv[x].size();i++){
if(rv[x][i]==st) {sz=dis+1;return;}
cch(rv[x][i],dis+1,st);
}
}
void dfs(int x,int dis,int st){
// cout<<st<<" "<<x<<" "<<dis<<" "<<k<<" "<<sz<<endl;
if(x%2==0 && (k%sz)==dis)
{
s.insert(x/2);
}
for(int i=0;i<rv[x].size();i++){
if(rv[x][i]==st) continue;
dfs(rv[x][i],dis+1,st);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int n=N,m=M,p=P;
for(int i=0;i<m;i++){///grafi1
int a=R[i][0];
int b=R[i][1];
v[a].push_back({i,b});
v[b].push_back({i,a});
}
for(int i=0;i<n;i++){
sort(v[i].begin(),v[i].end());
}
for(int i=0;i<n;i++){///grafi2
if(v[i].size()==1)
{
int to=v[i][0].second;
int val=v[i][0].first;
if(v[to][0].first==val)
v1[2*i+1]=2*to+1;
else
v1[2*i+1]=2*to;
if(v[to][0].first==val)
v1[2*i]=2*to+1;
else
v1[2*i]=2*to;
}
else
{
int to=v[i][0].second;
int val=v[i][0].first;
// cout<<i<<" "<<to<<" "<<val<<" "<<v[to][0].first<<endl;
if(v[to][0].first==val)
v1[2*i]=2*to+1;
else
v1[2*i]=2*to;
to=v[i][1].second;
val=v[i][1].first;
// cout<<i<<" "<<to<<" "<<val<<" "<<v[to][0].first<<endl;
if(v[to][0].first==val)
v1[2*i+1]=2*to+1;
else
v1[2*i+1]=2*to;
}
}
for(int i=0;i<2*n;i++){
//cout<<i<<" "<<v1[i]<<endl;
rv[v1[i]].push_back(i);
}
sz=100000000;cch(2*p,0,2*p);sz1=sz;
sz=100000000;cch(2*p+1,0,2*p+1);sz2=sz;
//cout<<sz1<<" "<<sz2<<endl;
for(int i=0; i<Q; i++)
{
k=G[i];
s.clear();
sz=sz1;dfs(2*p,0,2*p);
sz=sz2;dfs(2*p+1,0,2*p+1);
answer(s.size());
}
}
Compilation message
garden.cpp: In function 'void cch(int, int, int)':
garden.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<rv[x].size();i++){
~^~~~~~~~~~~~~
garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<rv[x].size();i++){
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
