#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=2e5+10;
const ll mod=1e9+7 ;
const ll base=2e9;
/// i believe myself
/// goal 2/7
#include "garden.h"
#include "gardenlib.h"
ll mx[maxn];
ll mx1[maxn];
ll dp[maxn][2][2];
ll col[maxn][2];
pll nxt[maxn][2];
pll ed;
void dfs(ll u,ll t)
{
col[u][t]=1;
auto p=nxt[u][t];
if (make_pair(u,t)==ed)
{
dp[u][t][t]=0;
return ;
}
if (!col[p.ff][p.ss])
{
dfs(p.ff,p.ss);
}
dp[u][t][ed.ss]=min(dp[u][t][ed.ss],dp[p.ff][p.ss][ed.ss]+1);
}
ll cnt=0;
void dfs1(ll u,ll t)
{
cnt++;
col[u][t]=1;
auto p=nxt[u][t];
if (col[p.ff][p.ss])
{
if (p!=ed)
{
cnt=base;
}
return ;
}
else
{
dfs1(p.ff,p.ss);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
ll n=N;
ll m=M;
for (int i=0; i<n; i++)
for (int t=0; t<=1; t++)
for (int t1=0; t1<=1; t1++)
mx[i]=base,mx1[i]=base,dp[i][t][t1]=base;
for (ll i=0; i<m; i++)
{
ll x=R[i][0];
ll y=R[i][1];
mx[x]=min(mx[x],i);
mx[y]=min(mx[y],i);
}
for (ll i=0; i<m; i++)
{
ll x=R[i][0];
ll y=R[i][1];
if (mx[x]!=i)
mx1[x]=min(mx1[x],i);
if (mx[y]!=i)
mx1[y]=min(mx1[y],i);
}
for (int i=0; i<n; i++)
{
ll nxt1=(R[mx[i]][0]+R[mx[i]][1]-i);
nxt[i][0]=make_pair(nxt1,(mx[i]==mx[nxt1]));
if (mx1[i]==base)
{
nxt[i][1]=nxt[i][0];
}
else
{
ll nxt1=(R[mx1[i]][0]+R[mx1[i]][1]-i);
nxt[i][1]=make_pair(nxt1,(mx1[i]==mx[nxt1]));
}
}
for (int t=0; t<=1; t++)
{
for (int i=0; i<n; i++)
for (int t=0; t<=1; t++)
col[i][t]=0;
ed=make_pair(P,t);
for (int i=0; i<n; i++)
{
for (int t=0; t<=1; t++)
{
if (!col[i][t])
dfs(i,t);
}
}
}
memset(col,0,sizeof(col));
ed=make_pair(P,0);
dfs1(P,0);
ll cnt0=cnt;
cnt=0;
memset(col,0,sizeof(col));
ed=make_pair(P,1);
dfs1(P,1);
ll cnt1=cnt;
for (int i=0; i<Q; i++)
{
ll x=G[i];
ll cnt=0;
for (int i=0; i<n; i++)
{
bool chk=false;
if (dp[i][0][0]!=base)
{
if (x>=dp[i][0][0]&&(x%cnt)==dp[i][0][0])
{
chk=true;
}
}
if (dp[i][0][1]!=base)
{
if (x>=dp[i][0][1]&&(x%cnt1)==dp[i][0][1])
{
chk=true;
}
}
cnt+=chk;
}
answer(cnt);
}
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
}
*/
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:119:8: warning: unused variable 'cnt0' [-Wunused-variable]
119 | ll cnt0=cnt;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
3796 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
3796 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
3796 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
