#include <bits/stdc++.h>
using namespace std;
#include "garden.h"
#include "gardenlib.h"
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
// #define MAX_M 1000000
// #define MAX_Q 2000
// static int N, M, P, Q;
// static int R[MAX_M][2];
// static int G[MAX_Q];
// static int solutions[MAX_Q];
// static int answers[MAX_Q];
// static int answer_count;
// inline
// void my_assert(int e) {if (!e) abort();}
// void read_input()
// {
// int i;
// my_assert(3==scanf("%d %d %d",&N,&M,&P));
// for(i=0; i<M; i++)
// my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
// my_assert(1==scanf("%d",&Q));
// for(i=0; i<Q; i++)
// my_assert(1==scanf("%d",&G[i]));
// for(i=0; i<Q; i++)
// my_assert(1==scanf("%d",&solutions[i]));
// }
// void answer(int x)
// {
// if(answer_count>=Q) {
// printf("Incorrect. Too many answers.\n");
// exit(0);
// }
// answers[answer_count] = x;
// answer_count++;
// }
lli n,m,d,g;
lli ed[300001][2],lim=30000000000000000,cur,ch=0,co=0,arr[2001],nex[300001],vis[300001],v2[300001];
vi al[300001];
vector<iii> pos[300001],v,v1;
lli lev[300001],ya=0;
bool cmp(lli a,lli b)
{
return (a%m)<(b%m);
}
void dfs1(lli node,int l)
{
lev[node]=l;
vis[node]=1;
if(!vis[nex[node]])
dfs1(nex[node],l+1);
else
{
if(v2[nex[node]]==-2)
{
cur=nex[node];
co=0;
while(1)
{
v2[cur]=3;
if(ed[cur][0]==d||ed[cur][1]==d)
v1.pb(mp(cur,mp((((ed[cur][0]==d)?0:1)),0)));
co++;
if(cur==node)
break;
cur=nex[cur];
}
for(int i=0;i<v1.size();++i)
v.pb(mp(v1[i].F,mp(v1[i].S.F,co)));
}
else
{
v2[node]=max(1*1LL,v2[node]);
ya=lev[nex[node]]-1;
for(int i=0;i<pos[nex[node]].size();++i)
v.pb(pos[nex[node]][i]);
}
}
if(ya!=-lim)
{
lev[node]=ya;
ya--;
}
v2[node]=max(1*1LL,v2[node]);
if(v2[node]!=3&&ed[node][0]==d||ed[node][1]==d)
v.pb(mp(node,mp((((ed[node][0]==d)?0:1)),lim)));
for(int i=0;i<v.size();++i)
pos[node].pb(v[i]);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n=N;
m=M;
d=P;
for(lli i=0;i<m;++i)
{
ed[i][0]=R[i][0];
ed[i][1]=R[i][1];
ed[i+m][0]=R[i][1];
ed[i+m][1]=R[i][0];
al[R[i][0]].pb(i);
al[R[i][1]].pb(i+m);
}
for(lli i=0;i<n;++i)
sort(all(al[i]),cmp);
g=Q;
for(lli i=0;i<g;++i)
arr[i]=G[i];
for(lli i=0;i<2*m;++i)
{
v2[i]=-2;
if(al[ed[i][1]].size()==1)
nex[i]=al[ed[i][1]][0];
else if((al[ed[i][1]][0]%m)!=(i%m))
nex[i]=al[ed[i][1]][0];
else
nex[i]=al[ed[i][1]][1];
}
memset(vis,0,sizeof(vis));
for(lli i=0;i<2*m;++i)
if(!vis[i])
{
v.clear();
v1.clear();
ya=-lim;
dfs1(i,0);
}
for(lli i=0;i<g;++i)
{
co=0;
for(lli j=0;j<n;++j)
{
for(int k=0;k<pos[al[j][0]].size();++k)
{
if(pos[al[j][0]].size()>5)
exit(1);
if(v2[al[j][0]]!=3||lev[al[j][0]]<=lev[pos[al[j][0]][k].F])
{
if(arr[i]>=(lev[pos[al[j][0]][k].F]-lev[al[j][0]]+pos[al[j][0]][k].S.F)&&(arr[i]-(lev[pos[al[j][0]][k].F]-lev[al[j][0]]+pos[al[j][0]][k].S.F))%pos[al[j][0]][k].S.S==0)
{
co++;
break;
}
}
else
{
if(arr[i]>=(pos[al[j][0]][k].S.F+pos[al[j][0]][k].S.S-(lev[al[j][0]]-lev[pos[al[j][0]][k].F]))&&(arr[i]-(pos[al[j][0]][k].S.F+pos[al[j][0]][k].S.S-(lev[al[j][0]]-lev[pos[al[j][0]][k].F])))%pos[al[j][0]][k].S.S==0)
{
co++;
break;
}
}
}
}
answer(co);
}
}
// int main()
// {
// int correct, i;
// read_input();
// answer_count = 0;
// count_routes(N,M,P,R,Q,G);
// if(answer_count!=Q) {
// printf("Incorrect. Too few answers.\n");
// exit(0);
// }
// correct = 1;
// for(i=0; i<Q; i++)
// if(answers[i]!=solutions[i])
// correct = 0;
// if(correct)
// printf("Correct.\n");
// else {
// printf("Incorrect.\n");
// printf("Expected: ");
// for(i=0; i<Q; i++)
// printf("%d ",solutions[i]);
// printf("\nReturned: ");
// for(i=0; i<Q; i++)
// printf("%d ",answers[i]);
// }
// return 0;
// }
Compilation message
garden.cpp: In function 'void dfs1(lli, int)':
garden.cpp:85:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<v1.size();++i)
| ~^~~~~~~~~~
garden.cpp:92:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i=0;i<pos[nex[node]].size();++i)
| ~^~~~~~~~~~~~~~~~~~~~~~
garden.cpp:102:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
102 | if(v2[node]!=3&&ed[node][0]==d||ed[node][1]==d)
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~
garden.cpp:104:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i=0;i<v.size();++i)
| ~^~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:150:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for(int k=0;k<pos[al[j][0]].size();++k)
| ~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
17152 KB |
Output is correct |
| 2 |
Correct |
12 ms |
17152 KB |
Output is correct |
| 3 |
Correct |
14 ms |
17152 KB |
Output is correct |
| 4 |
Correct |
11 ms |
16768 KB |
Output is correct |
| 5 |
Correct |
11 ms |
16768 KB |
Output is correct |
| 6 |
Correct |
13 ms |
17664 KB |
Output is correct |
| 7 |
Correct |
12 ms |
16896 KB |
Output is correct |
| 8 |
Correct |
12 ms |
17152 KB |
Output is correct |
| 9 |
Correct |
18 ms |
18944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
17152 KB |
Output is correct |
| 2 |
Correct |
12 ms |
17152 KB |
Output is correct |
| 3 |
Correct |
14 ms |
17152 KB |
Output is correct |
| 4 |
Correct |
11 ms |
16768 KB |
Output is correct |
| 5 |
Correct |
11 ms |
16768 KB |
Output is correct |
| 6 |
Correct |
13 ms |
17664 KB |
Output is correct |
| 7 |
Correct |
12 ms |
16896 KB |
Output is correct |
| 8 |
Correct |
12 ms |
17152 KB |
Output is correct |
| 9 |
Correct |
18 ms |
18944 KB |
Output is correct |
| 10 |
Correct |
11 ms |
16768 KB |
Output is correct |
| 11 |
Correct |
24 ms |
20224 KB |
Output is correct |
| 12 |
Correct |
46 ms |
23672 KB |
Output is correct |
| 13 |
Runtime error |
116 ms |
74788 KB |
Execution failed because the return code was nonzero |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
17152 KB |
Output is correct |
| 2 |
Correct |
12 ms |
17152 KB |
Output is correct |
| 3 |
Correct |
14 ms |
17152 KB |
Output is correct |
| 4 |
Correct |
11 ms |
16768 KB |
Output is correct |
| 5 |
Correct |
11 ms |
16768 KB |
Output is correct |
| 6 |
Correct |
13 ms |
17664 KB |
Output is correct |
| 7 |
Correct |
12 ms |
16896 KB |
Output is correct |
| 8 |
Correct |
12 ms |
17152 KB |
Output is correct |
| 9 |
Correct |
18 ms |
18944 KB |
Output is correct |
| 10 |
Correct |
11 ms |
16768 KB |
Output is correct |
| 11 |
Correct |
24 ms |
20224 KB |
Output is correct |
| 12 |
Correct |
46 ms |
23672 KB |
Output is correct |
| 13 |
Runtime error |
116 ms |
74788 KB |
Execution failed because the return code was nonzero |
| 14 |
Halted |
0 ms |
0 KB |
- |
