#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define cyc1 cyc
using namespace std;
const int N = 150010;
vector <array <int, 2>> g[N], gg[N];
int dist[N][2];
int low[N][2];
int nx[N][2];
int back[N][2];
void count_routes(int n, int m, int p, int r[][2], int q, int G[]){
for(int i = 0;i < m;i++){
gg[r[i][0]].push_back({i, r[i][1]});
gg[r[i][1]].push_back({i, r[i][0]});
}
memset(low, -1, sizeof low);
for(int i = 0;i < n;i++){
sort(gg[i].begin(), gg[i].end());
for(int j = 0;j < min((int)gg[i].size(), 2);j++){
g[gg[i][j][1]].push_back({gg[i][j][0], i});
low[i][j] = gg[i][j][0];
nx[i][j] = gg[i][j][1];
}
}
for(int i = 0;i < N;i++){
dist[i][0] = dist[i][1] = 1e9;
}
dist[p][0] = dist[p][1] = 0;
priority_queue <array <int, 3>> pq;
pq.push({0, p, 0});
pq.push({0, p, 1});
while(!pq.empty()){
auto [d, v, flag] = pq.top();
pq.pop();
d *= -1;
if(d != dist[v][flag]) continue;
for(auto [w, x] : g[v]){
if(w == low[x][0]){
int fg;
if(w == low[v][0]) fg = 1;
else fg = 0;
if(fg != flag) continue;
if(dist[v][flag]+1 < dist[x][0]){
dist[x][0] = dist[v][flag]+1;
if(v == p){
if(w == low[v][0]) back[x][0] = 1;
else back[x][0] = 0;
}
else{
back[x][0] = back[v][flag];
}
pq.push({-dist[x][0], x, 0});
if(low[x][1] == -1){
if(dist[v][flag]+1 < dist[x][1]){
dist[x][1] = dist[v][flag]+1;
if(v == p){
if(w == low[v][0]) back[x][1] = 1;
else back[x][1] = 0;
}
else{
back[x][1] = back[v][flag];
}
pq.push({-dist[x][1], x, 1});
}
}
}
}
else if(w == low[x][1]){
int fg;
if(w == low[v][0]) fg = 1;
else fg = 0;
if(fg != flag) continue;
if(dist[v][flag]+1 < dist[x][1]){
dist[x][1] = dist[v][flag]+1;
if(v == p){
if(w == low[v][0]) back[x][1] = 1;
else back[x][1] = 0;
}
else{
back[x][1] = back[v][flag];
}
pq.push({-dist[x][1], x, 1});
}
}
}
}
for(int i = 0;i < q;i++){
int k = G[i];
int res = 0;
for(int v = 0;v < n;v++){
if(dist[v][0] == k) {
res++;
continue;
}
if(k < dist[v][0]) continue;
int t = dist[v][0], b = back[v][0];
int cyc=0;
if(b == 0){
int x = nx[p][0];
cyc++;
if(low[p][0] == low[x][0]) cyc += dist[x][1];
else cyc += dist[x][0];
int bb = back[x][(low[p][0] == low[x][0] ? 1 : 0)];
if(bb == 0){
if(k % cyc == (dist[v][0]) % cyc){
res++;
continue;
}
else continue;
}
else{
int cyc2 = 0;
int xx = nx[p][1];
cyc2++;
if(low[p][1] == low[xx][0]) cyc2 += dist[xx][1];
else cyc2 += dist[xx][0];
int bbb = back[xx][(low[p][1] == low[xx][0] ? 1 : 0)];
if(bbb == 1){
if(k%cyc2 == (dist[v][0] + cyc1)%cyc2){
res++;
continue;
}
}
else{
if(k%(cyc1+cyc2) == (dist[v][0])%(cyc1+cyc2) or k%(cyc1+cyc2) == (dist[v][0]+cyc1)%(cyc1+cyc2)){
res++;
continue;
}
}
}
}
else{
int x = nx[p][1];
cyc++;
if(low[p][1] == low[x][0]) cyc += dist[x][1];
else cyc += dist[x][0];
int bb = back[x][(low[p][1] == low[x][0] ? 1 : 0)];
if(bb == 1){
if(k % cyc == (dist[v][0]) % cyc){
res++;
continue;
}
else continue;
}
else{
int cyc2 = 0;
int xx = nx[p][0];
cyc2++;
if(low[p][0] == low[xx][0]) cyc2 += dist[xx][1];
else cyc2 += dist[xx][0];
int bbb = back[xx][(low[p][0] == low[xx][0] ? 1 : 0)];
if(bbb == 0){
if(k%cyc2 == (dist[v][0] + cyc1)%cyc2){
res++;
continue;
}
}
else{
if(k%(cyc1+cyc2) == (dist[v][0])%(cyc1+cyc2) or k%(cyc1+cyc2) == (dist[v][0]+cyc1)%(cyc1+cyc2)){
res++;
continue;
}
}
}
}
}
answer(res);
}
}
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:100:13: warning: unused variable 't' [-Wunused-variable]
100 | int t = dist[v][0], b = back[v][0];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12832 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
12624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12832 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
12624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12832 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
12624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
