#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> graph[150005]; //just the normal graph
vector<int> adj[300005],cycles; //the graph with only one outgoing edge and each node twice
int best[150005],outgoing[300005],deg[300005],sizes[300005];
bool vis[300005],ans[300005];
void constructgraph(int N, int M, int R[][2]){
for(int i = 0;i<M;++i){
best[R[i][0]] = min(best[R[i][0]],i); //save the best trails for each node!
best[R[i][1]] = min(best[R[i][1]],i);
graph[R[i][0]].push_back({R[i][1],i}); //it's in decreasing order
graph[R[i][1]].push_back({R[i][0],i});
}
for(int i = 0;i<N;++i){
if(best[graph[i][0].first] == graph[i][0].second) outgoing[2*i] = graph[i][0].first*2+1;
else outgoing[2*i] = graph[i][0].first*2;
if(graph[i].size() == 1) outgoing[2*i+1] = outgoing[2*i];
else{
if(best[graph[i][1].first] == graph[i][1].second) outgoing[2*i+1] = graph[i][1].first*2+1;
else outgoing[2*i+1] = graph[i][1].first*2;
}
}
}
int dist0[15005],dist1[15005],peri0[15005],peri1[15005];
void finddist(int tar, int *dist, int *per){
queue<int> q,nq,nnq;
q.push(tar); nq.push(-1); nnq.push(0);
vis[tar] = true;
while(!q.empty()){
int qf = q.front(); q.pop();
int nqf = nq.front(); nq.pop();
int cdist = nnq.front(); nnq.pop();
nqf = max(nqf,sizes[qf]);
if(qf % 2 == 0){
dist[qf/2] = cdist;
per[qf/2] = nqf;
}
for(auto i : adj[qf]){
if(!vis[i]){
q.push(i);
nq.push(nqf);
nnq.push(cdist+1);
}
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
memset(best,0x3f,sizeof(best));
memset(deg,0,sizeof(deg));
memset(outgoing,0,sizeof(outgoing));
memset(sizes,-1,sizeof(sizes));
memset(dist0,-1,sizeof(dist0));
memset(dist1,-1,sizeof(dist1));
memset(peri0,-1,sizeof(peri0));
memset(peri1,-1,sizeof(peri1));
constructgraph(N,M,R);
//we need to find the cycles! Kahn's Algorithm?
for(int i = 0;i<2*N;++i){
deg[i]++;
deg[outgoing[i]]++;
}
queue<int> q;
for(int i = 0;i<2*N;++i){
if(deg[i] == 1) q.push(i);
}
while(!q.empty()){
int u = q.front(); q.pop();
deg[u]--; deg[outgoing[u]]--;
if(deg[outgoing[u]] == 1){
q.push(outgoing[u]);
}
}
for(int i = 0;i<2*N;++i){
adj[outgoing[i]].push_back(i);
if(deg[i]){ //cycle!
int cur = i;
while(deg[cur]){
deg[cur] = 0;
cycles.push_back(cur);
cur = outgoing[cur];
}
for(auto i : cycles) sizes[i] = (int)cycles.size();
}
}
//We still have to figure out the distances
finddist(2*P, dist0, peri0); finddist(2*P+1,dist1,peri1);
for(int i = 0;i<Q;++i){
int cnt = 0;
for(int j = 0;j<N;++j){
if(dist0[j] != -1){
if(peri0[j] == -1){
if(dist0[j] == G[i]){
cnt++; continue;
}
}
else{
if((G[i]-dist0[j])%peri0[j] == 0 && dist0[j]<=G[i]){
cnt++; continue;
}
}
}
if(dist1[j] != -1){
if(peri1[j] == -1){
if(dist1[j] == G[i]){
cnt++; continue;
}
}
else{
if((G[i]-dist1[j])%peri1[j] == 0 && dist1[j]<=G[i]){
cnt++; continue;
}
}
}
}
answer(cnt);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
