#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> graph[150005];
vector<int> adj[300005],cycle;
int best[150005],outgoing[300005],deg[300005],sizes[300005];
int dist0[150005],dist1[150005],peri0[150005],peri1[150005];
bool vis[300005];
void build(int N, int M, int R[][2]){
for(int i = 0;i<M;++i){
best[R[i][0]] = min(best[R[i][0]],i);
best[R[i][1]] = min(best[R[i][1]],i);
graph[R[i][0]].push_back({R[i][0],i});
graph[R[i][1]].push_back({R[i][1],i});
}
for(int i = 0;i<N;++i){
if(best[graph[i][0].first] == graph[i][0].second) outgoing[2*i] = 2*graph[i][0].first+1;
else outgoing[2*i] = 2*graph[i][0].first;
if(graph[i].size() == 1) outgoing[2*i] = outgoing[2*i+1];
else{
if(best[graph[i][1].first] == graph[i][1].second) outgoing[2*i+1] = 2*graph[i][1].first+1;
else outgoing[2*i+1] = 2*graph[i][1].first;
}
}
}
void calcdist(int src, int* dist, int* peri){
memset(vis,false,sizeof(vis));
queue<int> q,dq,pq; q.push(src); vis[src] = true;
dq.push(0); pq.push(-1);
while(!q.empty()){
int u = q.front(); q.pop();
int curdist = dq.front(); dq.pop();
int curper = pq.front(); pq.pop();
curper = max(curper,sizes[u]);
if(u % 2 == 0){
dist[u/2] = curdist;
peri[u/2] = curper;
}
for(auto v : adj[u]){
if(!vis[v]){
vis[v] = true;
q.push(v); dq.push(curdist+1);
pq.push(curper);
}
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
memset(best,0x3f,sizeof(best));
memset(sizes,-1,sizeof(sizes));
memset(peri0,-1,sizeof(peri0));
memset(peri1,-1,sizeof(peri1));
memset(dist0,-1,sizeof(dist0));
memset(dist1,-1,sizeof(dist1));
build(N,M,R);
for(int i = 0;i<2*N;++i){
deg[outgoing[i]]++;
deg[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.clear(); int v = i;
while(deg[v] != 0){
deg[v] = 0; cycle.push_back(v);
v = outgoing[i];
}
for(auto c : cycle) sizes[c] = (int)cycle.size();
}
}
calcdist(2*P,dist0,peri0); calcdist(2*P+1,dist1,peri1);
for(int i = 0;i<Q;++i){
int K = G[i], cnt = 0;
for(int j = 0;j<N;++j){
if(dist0[j] != -1){
if(peri0[j] == -1){
if(dist0[j] == K){
cnt++;
continue;
}
}
else{
if((K-dist0[j])%peri0[j] == 0 && dist0[j] <= K){
cnt++;
continue;
}
}
}
if(dist1[j] != -1){
if(peri1[j] == -1){
if(dist1[j] == K){
cnt++;
continue;
}
}
else{
if((K-dist1[j])%peri1[j] == 0 && dist1[j] <= K){
cnt++;
continue;
}
}
}
}
answer(cnt);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
15408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
15408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
15408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
