#include "garden.h"
#include "gardenlib.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
const int N=150050;
const int M=2*N;
//---------------------//
/*
void answer(int x){ printf("%i\n",x);}
*/
//---------------------//
int go[M],lo[M],dep[M];
vector<int> E[M];
void DFS(int u, int p)
{
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i];
dep[v]=dep[u]+1;
if(v!=p) DFS(v,p);
}
}
pair<int,int> Qs[N];
int cnt[M],sol[N];
void count_routes(int n, int m, int p, int r[][2], int q, int k[])
{
int i,j;
for(i=0;i<q;i++) Qs[i].first=k[i],Qs[i].second=i;
sort(Qs,Qs+q);
for(i=0;i<n*2;i++) lo[i]=-1;
for(i=0;i<n*2;i++) go[i]=-1;
for(i=0;i<m;i++)
{
if(lo[r[i][0]<<1]==-1) lo[r[i][0]<<1]=i;
else if(lo[r[i][0]<<1|1]==-1) lo[r[i][0]<<1|1]=i;
if(lo[r[i][1]<<1]==-1) lo[r[i][1]<<1]=i;
else if(lo[r[i][1]<<1|1]==-1) lo[r[i][1]<<1|1]=i;
}
for(i=0;i<n*2;i++)
{
int x=lo[i];
if(lo[i]==-1) x=lo[i^1];
int v=r[x][0];
if(v==i/2) v=r[x][1];
if(x==lo[v<<1]) go[i]=v<<1|1;
else go[i]=v<<1;
}
for(i=0;i<2*n;i++)
{
E[go[i]].pb(i);
//printf("%i -> %i\n",go[i],i);
dep[i]=-1;
}
dep[p<<1]=0;
DFS(p<<1,p<<1);
if(dep[p<<1]==0)
{
for(i=0;i<2*n;i+=2) if(dep[i]!=-1) cnt[dep[i]]++;
for(i=0;i<q;i++) sol[i]+=cnt[k[i]];
for(i=0;i<2*n;i+=2) if(dep[i]!=-1) cnt[dep[i]]--;
}
else
{
int cyc=dep[p<<1];
j=0;
vector<int> Ds;
for(i=0;i<2*n;i+=2) if(dep[i]!=-1) Ds.pb(dep[i]);
sort(Ds.begin(),Ds.end());
for(i=0;i<q;i++)
{
while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
sol[Qs[i].second]+=cnt[Qs[i].first%cyc];
}
for(i=0;i<cyc;i++) cnt[i]=0;
}
for(i=0;i<2*n;i++) dep[i]=-1;
dep[p<<1|1]=0;
DFS(p<<1|1,p<<1|1);
if(dep[p<<1|1]==0)
{
for(i=0;i<2*n;i+=2) if(dep[i]!=-1) cnt[dep[i]]++;
for(i=0;i<q;i++) sol[i]+=cnt[k[i]];
for(i=0;i<2*n;i+=2) if(dep[i]!=-1) cnt[dep[i]]--;
}
else
{
int cyc=dep[p<<1|1];
//printf("%i :D\n",cyc);
j=0;
vector<int> Ds;
for(i=0;i<2*n;i+=2) if(dep[i]!=-1) Ds.pb(dep[i]);
sort(Ds.begin(),Ds.end());
for(i=0;i<q;i++)
{
while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
sol[Qs[i].second]+=cnt[Qs[i].first%cyc];
}
for(i=0;i<cyc;i++) cnt[i]=0;
}
for(i=0;i<q;i++) answer(sol[i]);
}
//---------------------//
/*
int r[N][2],k[N];
int main()
{
int n,m,p,q,i;
scanf("%i %i %i",&n,&m,&p);
for(i=0;i<m;i++) scanf("%i %i",&r[i][0],&r[i][1]);
scanf("%i",&q);
for(i=0;i<q;i++) scanf("%i",&k[i]);
count_routes(n,m,p,r,q,k);
return 0;
}
*/
//---------------------//
Compilation message
garden.cpp: In function 'void DFS(int, int)':
garden.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<E[u].size();i++)
~^~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:74:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
~^~~~~~~~~~
garden.cpp:98:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7568 KB |
Output is correct |
2 |
Correct |
8 ms |
7484 KB |
Output is correct |
3 |
Correct |
8 ms |
7544 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
8 ms |
7396 KB |
Output is correct |
6 |
Correct |
9 ms |
7640 KB |
Output is correct |
7 |
Correct |
8 ms |
7388 KB |
Output is correct |
8 |
Correct |
9 ms |
7484 KB |
Output is correct |
9 |
Correct |
7 ms |
7544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7568 KB |
Output is correct |
2 |
Correct |
8 ms |
7484 KB |
Output is correct |
3 |
Correct |
8 ms |
7544 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
8 ms |
7396 KB |
Output is correct |
6 |
Correct |
9 ms |
7640 KB |
Output is correct |
7 |
Correct |
8 ms |
7388 KB |
Output is correct |
8 |
Correct |
9 ms |
7484 KB |
Output is correct |
9 |
Correct |
7 ms |
7544 KB |
Output is correct |
10 |
Correct |
9 ms |
7376 KB |
Output is correct |
11 |
Correct |
19 ms |
9148 KB |
Output is correct |
12 |
Correct |
33 ms |
10052 KB |
Output is correct |
13 |
Correct |
73 ms |
24848 KB |
Output is correct |
14 |
Correct |
104 ms |
17296 KB |
Output is correct |
15 |
Correct |
141 ms |
18368 KB |
Output is correct |
16 |
Correct |
111 ms |
15508 KB |
Output is correct |
17 |
Runtime error |
83 ms |
27232 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7568 KB |
Output is correct |
2 |
Correct |
8 ms |
7484 KB |
Output is correct |
3 |
Correct |
8 ms |
7544 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
8 ms |
7396 KB |
Output is correct |
6 |
Correct |
9 ms |
7640 KB |
Output is correct |
7 |
Correct |
8 ms |
7388 KB |
Output is correct |
8 |
Correct |
9 ms |
7484 KB |
Output is correct |
9 |
Correct |
7 ms |
7544 KB |
Output is correct |
10 |
Correct |
9 ms |
7376 KB |
Output is correct |
11 |
Correct |
19 ms |
9148 KB |
Output is correct |
12 |
Correct |
33 ms |
10052 KB |
Output is correct |
13 |
Correct |
73 ms |
24848 KB |
Output is correct |
14 |
Correct |
104 ms |
17296 KB |
Output is correct |
15 |
Correct |
141 ms |
18368 KB |
Output is correct |
16 |
Correct |
111 ms |
15508 KB |
Output is correct |
17 |
Runtime error |
83 ms |
27232 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
18 |
Halted |
0 ms |
0 KB |
- |