#include "garden.h"
#include <bits/stdc++.h>
#include "gardenlib.h"
using namespace std;
const int MAXN = 4e5;
vector<int>g[MAXN],adj[MAXN];
int jump[MAXN],cycle[MAXN],col[MAXN],dist[MAXN],vis[MAXN],ans[MAXN];
void dfs(int v){
col[v] = 1;
if(col[jump[v]] ==1)cycle[v] = 1;
else if(!col[jump[v]])dfs(jump[v]);
col[v] = 2;
}
void dfs2(int v){
vis[v] = 1;
for(int x:adj[v]){
if(!vis[x]){
dist[x] = dist[v]+1;
dfs2(x);
}
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int G[])
{
for(int i=0;i<m;i++){
g[r[i][0]].push_back(r[i][1]);
g[r[i][1]].push_back(r[i][0]);
}
for(int i=0;i<n;i++){
//2*i -> most beautiful route wasnt taken last turn
//2*i+1 ->most beautiful route was taken
int v = g[i][0];
if(g[v][0] != i)jump[2*i] = 2*v;
else jump[2*i] = 2*v+1;
int s = g[i].size();
if(s > 1)v = g[i][1];
if(g[v][0] != i)jump[2*i+1] = 2*v;
else jump[2*i+1] = 2*v+1;
}
for(int i=0;i<2*n;i++){
if(!col[i])dfs(i);
if(cycle[i]){
int v = jump[i];
while(!cycle[v]){
cycle[v] = 1;
v = jump[v];
}
}
adj[jump[i]].push_back(i);
dist[i] = 1e9;
}
//for(int i=0;i<2*n;i++)cout<<cycle[i]<<" ";
//cout<<'\n';
//for(int i=0;i<2*n;i++)cout<<jump[i]<<" ";
cout<<'\n';
dist[2*p] = 0;
dfs2(2*p);
if(!cycle[2*p]){
vector<int>cnt(n+1,0);
for(int i=0;i<n;i++){
if(dist[2*i] != 1e9)cnt[dist[2*i]]++;
}
for(int i=0;i<q;i++){
if(G[i]<=n)ans[i]+=cnt[G[i]];
}
}else{
int len = 0;
int v = 2*p;
while(cycle[v]==1){
len++;
v = jump[v];
cycle[v]++;
}
vector<vector<int>>mod(n);
for(int i=0;i<n;i++){
if(dist[2*i] != 1e9){
int x = dist[2*i];
mod[x%len].push_back(x);
}
}
for(int i=0;i<len;i++)sort(mod[i].begin(),mod[i].end());
for(int i=0;i<q;i++){
int rem = G[i]%len;
if(mod[rem].empty())continue;
int pt = upper_bound(mod[rem].begin(),mod[rem].end(),G[i]) - mod[rem].begin();
ans[i]+=pt;
}
}
for(int i=0;i<2*n;i++)dist[i] = 1e9;
dist[2*p+1] = 0;
dfs2(2*p+1);
if(!cycle[2*p+1]){
vector<int>cnt(n+1,0);
for(int i=0;i<n;i++){
if(dist[2*i] != 1e9)cnt[dist[2*i]]++;
}
for(int i=0;i<q;i++){
if(G[i]<=n)ans[i]+=cnt[G[i]];
}
}else{
int len = 0;
int v = 2*p+1;
while(cycle[v]){
len++;
cycle[v] = 0;
v = jump[v];
}
//cout<<len<<'\n';
//for(int i=0;i<n;i++)cout<<dist[2*i]<<" ";
//cout<<'\n';
vector<vector<int>>mod(len);
for(int i=0;i<n;i++){
if(dist[2*i] != 1e9){
int x = dist[2*i];
mod[x%len].push_back(x);
}
}
for(int i=0;i<len;i++)sort(mod[i].begin(),mod[i].end());
for(int i=0;i<q;i++){
int rem = G[i]%len;
if(mod[rem].empty())continue;
int pt = upper_bound(mod[rem].begin(),mod[rem].end(),G[i]) - mod[rem].begin();
ans[i]+=pt;
}
}
for(int i=0;i<q;i++)answer(ans[i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
