#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
//answer(N) -- query
int n;
int INF = 1e9;
int p;
vector<vector<int>> adjlist;
vector<vector<pair<int,int>>> dp;
//node, comes from beautiful
//until k, type of k visit
//-1 - never cycles, 0 - returns unblocked, 1 - returns blocked
pair<int,bool> genk(int node, bool blocked, bool start){
//cout<<node<<" "<<blocked<<'\n';
if (node==p&&!start){
//we've found p
return {0,blocked};
}
if (dp[node][blocked].first!=-1){
return dp[node][blocked];
}
if (dp[node][blocked].second==true){
//we've reached a cycle
return dp[node][blocked]={INF,-1};
}
dp[node][blocked].second = true; //to check for cycles
int next = adjlist[node][0];
if (adjlist[node].size()>1&&blocked){
next = adjlist[node][1];
}
bool isBlocked = adjlist[next][0]==node;
pair<int,bool> ans = genk(next,isBlocked,false);
if (ans.first==INF){
return dp[node][blocked]={INF,-1};
} else {
return dp[node][blocked]={ans.first+1,ans.second};
}
}
pair<int,int> followpath(int node, bool blocked){
if (node==p){
return {0,blocked};
}
if (dp[node][blocked].first!=-1){
return dp[node][blocked];
}
if (dp[node][blocked].second==true){
//we've reached a bad cycle
return dp[node][blocked]={INF,false};
}
dp[node][blocked].second = true; //to check for cycles
int next = adjlist[node][0];
if (adjlist[node].size()>1&&blocked){
next = adjlist[node][1];
}
bool isBlocked = adjlist[next][0]==node;
pair<int,int> ans = followpath(next,isBlocked);
if (ans.first==INF){
return dp[node][blocked]={INF,false};
} else {
return dp[node][blocked]={ans.first+1,ans.second};
}
}
bool routeExists(int i, int val){
if (dp[i][0].first>=INF){
return false;
}
/*if (dp[i][0].first==val){
return true;
}*/
bool b = dp[i][0].second;
if (dp[p][b].first>=INF){
//X->?
return val==dp[i][0].first;
} else if (dp[p][b].second==b){
//X->X
val-=dp[i][0].first;
return val%dp[p][b].first==0;
} else {
val-=dp[i][0].first;
//X->Y
if (val==0){return true;}
if (dp[p][!b].first>=INF){
//X->Y->?
return val==dp[p][b].first;
} else if (dp[p][!b].second==!b){
//X->Y->Y
val-=dp[p][b].first;
return val%dp[p][!b].first==0;
} else {
//X->Y->X
val%=(dp[p][b].first+dp[p][!b].first);
return (val==0||val==dp[p][b].first);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n=N;p=P;
adjlist.resize(n);
dp.resize(n,vector<pair<int,int>>(2,{-1,false}));
for (int i = 0; i<M; i++){
adjlist[R[i][0]].push_back(R[i][1]);
adjlist[R[i][1]].push_back(R[i][0]);
}
//cout<<"gen\n";
genk(p,false,true);
//cout<<dp[p][0].first<<'\n';
//cout<<"gen\n";
genk(p,true,true);
//cout<<dp[p][1].first<<'\n';
for (int i = 0; i<n; i++){
for (int blocked = 0; blocked<2; blocked++){
if (dp[i][blocked].first==-1){
followpath(i,blocked);
}
}
}
//todo: check for case where inf
for (int q = 0; q<Q; q++){
int cnt = 0;
int val = G[q];
for (int i = 0; i<n; i++){
if (routeExists(i,val)){
cnt++;
}
}
answer(cnt);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
