#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=150000, INF = 1000000000;
int edges[2*MAXN][2];
bool open[MAXN][2];
vector<int> adj[MAXN]; /// value is index/2, want minimum next one
pair<int, int> ds[MAXN], df[MAXN];
void go12(int at);
void go11 (int at) {
if (df[at].a != INF) return;
if (open[at][0]) {df[at].a = -INF; return;}
open[at][0] = true;
int n1 = adj[at][0]; /// edge
int x = edges[n1][1]; /// node
//w<< "at11" c at<<e;
go11 (x); go12(x);
/// set df[at]
int nex = adj[x][0]/2; /// edge
if (n1/2 == nex) df[at].a = 1+ds[x].a;
else df[at].a = 1+df[x].a;
open[at][0] = false;
}
void go12 (int at) {
if (ds[at].a != INF) return;
if (open[at][1]) {ds[at].a = -INF; return;}
open[at][1] = true;
int n1 = adj[at][1]; /// edge
int x = edges[n1][1]; /// node
//w<< "at12" c at<<e;
go11 (x); go12(x);
/// set ds[at]
int nex = adj[x][0]/2; /// edge
if (n1/2 == nex) ds[at].a = 1+ds[x].a;
else ds[at].a = 1+df[x].a;
open[at][1] = false;
}
void go22(int at);
void go21 (int at) {
if (df[at].b != INF) return;
if (open[at][0]) {df[at].b = -INF; return;}
open[at][0] = true;
int n1 = adj[at][0]; /// edge
int x = edges[n1][1]; /// node
//w<< "at11" c at<<e;
go21 (x); go22(x);
/// set df[at]
int nex = adj[x][0]/2; /// edge
if (n1/2 == nex) df[at].b = 1+ds[x].b;
else df[at].b = 1+df[x].b;
open[at][0] = false;
}
void go22 (int at) {
if (ds[at].b != INF) return;
if (open[at][1]) {ds[at].b = -INF; return;}
open[at][1] = true;
int n1 = adj[at][1]; /// edge
int x = edges[n1][1]; /// node
//w<< "at12" c at<<e;
go21 (x); go22(x);
/// set ds[at]
int nex = adj[x][0]/2; /// edge
if (n1/2 == nex) ds[at].b = 1+ds[x].b;
else ds[at].b = 1+df[x].b;
open[at][1] = false;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
for (int j=M-1; j>=0; j--) {
edges[2*j][0] = edges[2*j+1][1] = R[j][0];
edges[2*j][1] = edges[2*j+1][0] = R[j][1];
adj[R[j][0]].pb(2*j);
adj[R[j][1]].pb(2*j+1);
}
ffi {
sort(adj[i].begin(), adj[i].end());
while (adj[i].size() > 2) adj[i].pop_back();
if (adj[i].size() == 1) adj[i].pb(adj[i][0]); /// repeat the element
ds[i] = df[i] = mp(INF, INF);
}
ds[P].a = df[P].a = 0; /// we are already at P
ffi go11(i), go12(i);
//ffi w<< i c df[i].a s ds[i].a <<e;
/// set df[P].b
int n1 = adj[P][0]; /// edge
int x = edges[n1][1]; /// node
int nex = adj[x][0]/2; /// edge
if (n1/2 == nex) df[P].b = 1+ds[x].a;
else df[P].b = 1+df[x].a;
/// set ds[P].b
n1 = adj[P][1]; /// edge
x = edges[n1][1]; /// node
nex = adj[x][0]/2; /// edge
if (n1/2 == nex) ds[P].b = 1+ds[x].a;
else ds[P].b = 1+df[x].a;
ffi open[i][0] = open[i][1] = false;
ffi go21(i), go22(i);
//ffi w<< i c df[i].b s ds[i].b <<e;
for(int i=0; i<Q; i++) {
int x = G[i];
int out = 0;
ffj {
if (x == df[j].a) out++;
else if (x < df[j].a) {}
else if (df[j].b != df[j].a && (x-df[j].a) % (df[j].b - df[j].a) == 0) out++;
}
//w<< "got" s i c out<<e;
answer(out);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3960 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3960 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3832 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3932 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
3960 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3960 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3960 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3832 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3932 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
3960 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3960 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3960 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3832 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3932 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
3960 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
