#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define oo 1e9
using namespace std;
bool comp(pii a, pii b){
return a.second < b.second;
}
const int MAX = 3e5 + 5;
int n, m, f;
vector<pii> g[MAX];
int tmpG[MAX];
int revG[MAX];
pii dist[MAX];
int dfs(int node, int d){
if(revG[node] != f && dist[revG[node]].first < d + 1) return 0;
dist[node].first = min(dist[node].first, d);
int c = 0;
if(revG[node] == f){
c = d + 1;
}
else{
c = dfs(revG[node], d + 1);
}
if(c){
dist[node].second = c - dist[node].first;
}
return c;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
fill(dist, dist + MAX, make_pair(oo, oo));
f = P;
n = N;
m = M;
for (int i = 0; i < m; i++)
{
g[R[i][0]].push_back({R[i][1], i});
g[R[i][1]].push_back({R[i][0], i});
}
for (int i = 0; i < n; i++)
{
sort(g[i].begin(), g[i].end(), comp);
}
for (int i = 0; i < n; i++)
{
if(g[i][0].second == g[g[i][0].first][0].second){
tmpG[i] = g[i][0].first + n;
}
else{
tmpG[i] = g[i][0].first;
}
if(g[i].size() >= 2){
if(g[i][1].second == g[g[i][1].first][0].second){
tmpG[i + n] = g[i][1].first + n;
}
else{
tmpG[i + n] = g[i][1].first;
}
}
if(g[i].size() == 1){
tmpG[i + n] = tmpG[i];
}
}
for (int i = 0; i < (n << 1); i++)
{
revG[tmpG[i]] = i;
}
dfs(f, 0);
dfs(f + n, 0);
for (int j = 0; j < Q; j++)
{
int ans = 0;
for (int i = 0; i < (n << 1); i++)
{
if(dist[i].first == oo) continue;
if(dist[i].second == oo) ans += (dist[i].first == G[j]);
else if(G[j] - dist[i].first >= 0) ans += ((G[j] - dist[i].first) % dist[i].second) == 0;
}
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
