#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
const int N=150005;
const int M=300005;
const int inf=2e9;
int n,p;
vector<int> padj[N];
vector<pair<int,int>> adj[N][2];
int dp[2][N][2];
int cnt[2][M];
int cyc[2];
void dfs(int t,int u,int s,int d=0){
dp[t][u][s]=d;
for(auto [v,w]:adj[u][s]){
if(v==p&&w==t){
cyc[t]=d+1;
}else{
dfs(t,v,w,d+1);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n=N,p=P;
for(int t=0;t<2;t++)for(int i=0;i<n;i++)dp[t][i][0]=dp[t][i][1]=inf;
for(int i=0;i<M;i++){
int u=R[i][0],v=R[i][1];
padj[u].emplace_back(v);
padj[v].emplace_back(u);
}
for(int u=0;u<n;u++){
for(int s=0;s<2;s++){
int v=padj[u][min(s,(int)padj[u].size()-1)];
adj[v][padj[v][0]==u].emplace_back(u,s);
}
}
for(int t=0;t<2;t++){
dfs(t,p,t);
for(int i=0;i<n;i++){
int d=dp[t][i][0];
if(d==inf)continue;
cnt[t][d]++;
}
if(cyc[t]){
for(int i=cyc[t];i<=2*n;i++)cnt[t][i]+=cnt[t][i-cyc[i]];
}
}
for(int i=0;i<Q;i++){
int k=G[i];
int ans=0;
for(int t=0;t<2;t++){
if(k<=2*n)ans+=cnt[t][k];
else if(cyc[t]){
int d=k-2*n;
d=(d+cyc[t]-1)/cyc[t]*cyc[t];
ans+=cnt[t][k-d];
}
}
answer(ans);
}
}
Compilation message
garden.cpp: In function 'void dfs(int, int, int, int)':
garden.cpp:20:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
20 | for(auto [v,w]:adj[u][s]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
11092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
11092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
11092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
