#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=1e6;
vector<pii> vec[MAX];
int P_,lol,deg[MAX],res[MAX];
int type[MAX],Distance[MAX];
int Min[MAX],SecMin[MAX],mark[MAX][2];
pii dp[2];
bool cal(int X,int Y)
{
return (X>=0 and Y>0 and X%Y==0);
}
void dfs(int node,int types,int dis)
{
if(node==P_)
return ;
else if(types==1)
{
type[node]=lol;
Distance[node]=dis;
for(auto A:vec[node])
{
if(deg[node]>1 and A.first==Min[node])
continue;
dfs(A.first,A.second,dis+1);
}
return ;
}
else if(types==2)
{
for(auto A:vec[node])
if(A.first==Min[node])
dfs(A.first,A.second,dis+1);
return ;
}
return ;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
P_=P;
int u,v;
for(int A=0;A<N;A++)
{
Min[A]=-1;
SecMin[A]=-1;
type[A]=-1;
Distance[A]=-1;
}
for(int A=0;A<M;A++)
{
u=R[A][0];
v=R[A][1];
if(deg[u]<2)
{
++deg[u];
vec[v].pb(mp(u,deg[u]));
}
if(deg[v]<2)
{
++deg[v];
vec[u].pb(mp(v,deg[v]));
}
if(Min[u]!=-1 and SecMin[u]==-1)
SecMin[u]=v;
if(Min[v]!=-1 and SecMin[v]==-1)
SecMin[v]=u;
if(Min[u]==-1)
Min[u]=v;
if(Min[v]==-1)
Min[v]=u;
}
Distance[P]=0;
type[P]=0;
for(auto A:vec[P])
{
lol=(A.first==Min[P]);
dfs(A.first,A.second,1);
}
dp[0]=mp(-1,0);
dp[1]=mp(-1,0);
int cur=P,pre=-1;
while(true)
{
dp[0].second++;
if(deg[cur]>1 and Min[cur]==pre)
{
if(mark[cur][0])
break;
mark[cur][0]=1;
pre=cur;
cur=SecMin[cur];
}
else
{
if(mark[cur][1])
break;
mark[cur][1]=1;
pre=cur;
cur=Min[cur];
}
if(cur==P)
{
dp[0].first=(pre==Min[P]);
break;
}
}
for(int A=0;A<N;A++)
{
mark[A][0]=0;
mark[A][1]=0;
}
if(deg[P]>1)
{
pre=P;
cur=SecMin[P];
dp[1].second++;
while(true)
{
dp[1].second++;
if(deg[cur]>1 and Min[cur]==pre)
{
if(mark[cur][0])
break;
mark[cur][0]=1;
pre=cur;
cur=SecMin[cur];
}
else
{
if(mark[cur][1])
break;
mark[cur][1]=1;
pre=cur;
cur=Min[cur];
}
if(cur==P)
{
dp[1].first=(pre==Min[P]);
break;
}
}
}
int ok,final;
for(int A=0;A<Q;A++)
{
for(int B=0;B<N;B++)
{
if(Distance[B]==-1)
continue;
ok=0;
final=G[A];
ok|=(Distance[B]==final);
final-=Distance[B];
if(type[B]==0 or deg[P]==1) //We'll exit for first time using Min
{
final-=Distance[B];
if(dp[0].first==1 and dp[1].first==0)// Min-SecMin-Min-SecMin
{
ok|=cal(final,dp[0].second+dp[1].second);
final-=dp[0].second;
ok|=cal(final,dp[0].second+dp[1].second);
}
else if(dp[0].first==1 and dp[1].first==1)// Min-SecMin-SecMin-SecMin
{
final-=dp[0].second;
ok|=cal(final,dp[1].second);
}
else if(dp[0].first==0)// Min-Min-Min
{
ok|=cal(final,dp[0].second);
}
}
else if(type[B]==1) //We'll exit this time using SecMin
{
final-=Distance[B];
if(dp[1].first==0 and dp[0].first==1)// SecMin-Min-SecMin-Min
{
ok|=cal(final,dp[1].second+dp[0].second);
final-=dp[1].second;
ok|=cal(final,dp[1].second+dp[0].second);
}
else if(dp[1].first==0 and dp[0].first==0)// SecMin-Min-Min-Min
{
final-=dp[1].second;
ok|=cal(final,dp[0].second);
}
else if(dp[1].first==1)//SecMin-SecMin-SecMin
{
ok|=cal(final,dp[1].second);
}
}
res[A]+=ok;
}
}
for(int A=0;A<Q;A++)
answer(res[A]);
// cout<<res[A]<<"\n";
return ;
}
/*signed main()
{
ios_base::sync_with_stdio(false);
int G[]={3};
int R[][2]={{1,2},{0,1},{0,3},{3,4},{4,5},{1,5}};
count_routes(6,6,0,R,1,G);
return 0;
}*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
24016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
24016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
24016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
