#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;
queue<int> q, p, d;
vector<int> ls;
vector<pi> graph[150005];
vector<int> graph1[300005];
int nxt[300005];
int low[150005];
int deg[300005];
int ped[300005];
bool vis[300005];
bool ans[150005];
void make_graph(int N, int M, int R[][2]){
for (int i=0; i<M; i++) {
for (int j=0; j<2; j++) {
low[R[i][j]] = min(low[R[i][j]],i);
}
graph[R[i][0]].push_back(pi(R[i][1],i));
graph[R[i][1]].push_back(pi(R[i][0],i));
}
for (int i=0; i<N; i++) {
if(low[graph[i][0].first] == graph[i][0].second){
nxt[2*i] = graph[i][0].first * 2 + 1;
}
else{
nxt[2*i] = graph[i][0].first * 2;
}
if(graph[i].size() == 1){
nxt[2*i+1] = nxt[2*i];
}
else{
if(low[graph[i][1].first] == graph[i][1].second){
nxt[2*i+1] = graph[i][1].first * 2 + 1;
}
else{
nxt[2*i+1] = graph[i][1].first * 2;
}
}
}
}
void solve(int x, int g){
memset(vis,0,sizeof(vis));
q.push(x);
p.push(-1);
d.push(0);
vis[x] = 1;
while (!q.empty()) {
int qf = q.front();
int pf = p.front();
int df = d.front();
q.pop(), p.pop(), d.pop();
pf = max(pf, ped[qf]);
if(qf % 2 == 0){
if(pf == -1){
if(df == g){
ans[qf/2] = 1;
}
}
else{
if(df <= g && (g - df) % pf == 0){
ans[qf/2] = 1;
}
}
}
for (auto &i : graph1[qf]){
if(!vis[i]){
vis[i] = 1;
q.push(i);
p.push(pf);
d.push(df + 1);
}
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
memset(ped,-1,sizeof(ped));
memset(low,0x3f,sizeof(low));
make_graph(N,M,R);
for (int i=0; i<2*N; i++) {
deg[i]++;
deg[nxt[i]]++;
}
for (int i=0; i<2*N; i++) {
if(deg[i] == 1){
q.push(i);
}
}
while (!q.empty()) {
int qf = q.front();
q.pop();
deg[qf]--;
deg[nxt[qf]]--;
if(deg[nxt[qf]] == 1){
q.push(nxt[qf]);
}
}
for (int i=0; i<2*N; i++) {
graph1[nxt[i]].push_back(i);
if(deg[i]){
int pos = i;
ls.clear();
while (deg[pos]) {
deg[pos] = 0;
ls.push_back(pos);
pos = nxt[pos];
}
for (auto &i : ls){
ped[i] = (int)ls.size();
}
}
}
for (int i=0; i<Q; i++) {
memset(ans,0,sizeof(ans));
solve(2*P,G[i]);
solve(2*P+1,G[i]);
int cnt = 0;
for (int j=0; j<N; j++) {
if(ans[j]) cnt++;
}
answer(cnt);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
13144 KB |
Output is correct |
2 |
Correct |
14 ms |
13148 KB |
Output is correct |
3 |
Correct |
14 ms |
13276 KB |
Output is correct |
4 |
Correct |
13 ms |
13048 KB |
Output is correct |
5 |
Correct |
13 ms |
13048 KB |
Output is correct |
6 |
Correct |
14 ms |
13276 KB |
Output is correct |
7 |
Correct |
13 ms |
13048 KB |
Output is correct |
8 |
Correct |
14 ms |
13236 KB |
Output is correct |
9 |
Correct |
16 ms |
13372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
13144 KB |
Output is correct |
2 |
Correct |
14 ms |
13148 KB |
Output is correct |
3 |
Correct |
14 ms |
13276 KB |
Output is correct |
4 |
Correct |
13 ms |
13048 KB |
Output is correct |
5 |
Correct |
13 ms |
13048 KB |
Output is correct |
6 |
Correct |
14 ms |
13276 KB |
Output is correct |
7 |
Correct |
13 ms |
13048 KB |
Output is correct |
8 |
Correct |
14 ms |
13236 KB |
Output is correct |
9 |
Correct |
16 ms |
13372 KB |
Output is correct |
10 |
Correct |
13 ms |
13076 KB |
Output is correct |
11 |
Correct |
29 ms |
15360 KB |
Output is correct |
12 |
Correct |
54 ms |
17216 KB |
Output is correct |
13 |
Correct |
66 ms |
23796 KB |
Output is correct |
14 |
Correct |
180 ms |
26144 KB |
Output is correct |
15 |
Correct |
227 ms |
26544 KB |
Output is correct |
16 |
Correct |
163 ms |
23200 KB |
Output is correct |
17 |
Correct |
169 ms |
22488 KB |
Output is correct |
18 |
Correct |
53 ms |
17140 KB |
Output is correct |
19 |
Correct |
178 ms |
26144 KB |
Output is correct |
20 |
Correct |
207 ms |
26528 KB |
Output is correct |
21 |
Correct |
163 ms |
23164 KB |
Output is correct |
22 |
Correct |
157 ms |
22428 KB |
Output is correct |
23 |
Correct |
176 ms |
27308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
13144 KB |
Output is correct |
2 |
Correct |
14 ms |
13148 KB |
Output is correct |
3 |
Correct |
14 ms |
13276 KB |
Output is correct |
4 |
Correct |
13 ms |
13048 KB |
Output is correct |
5 |
Correct |
13 ms |
13048 KB |
Output is correct |
6 |
Correct |
14 ms |
13276 KB |
Output is correct |
7 |
Correct |
13 ms |
13048 KB |
Output is correct |
8 |
Correct |
14 ms |
13236 KB |
Output is correct |
9 |
Correct |
16 ms |
13372 KB |
Output is correct |
10 |
Correct |
13 ms |
13076 KB |
Output is correct |
11 |
Correct |
29 ms |
15360 KB |
Output is correct |
12 |
Correct |
54 ms |
17216 KB |
Output is correct |
13 |
Correct |
66 ms |
23796 KB |
Output is correct |
14 |
Correct |
180 ms |
26144 KB |
Output is correct |
15 |
Correct |
227 ms |
26544 KB |
Output is correct |
16 |
Correct |
163 ms |
23200 KB |
Output is correct |
17 |
Correct |
169 ms |
22488 KB |
Output is correct |
18 |
Correct |
53 ms |
17140 KB |
Output is correct |
19 |
Correct |
178 ms |
26144 KB |
Output is correct |
20 |
Correct |
207 ms |
26528 KB |
Output is correct |
21 |
Correct |
163 ms |
23164 KB |
Output is correct |
22 |
Correct |
157 ms |
22428 KB |
Output is correct |
23 |
Correct |
176 ms |
27308 KB |
Output is correct |
24 |
Correct |
90 ms |
13180 KB |
Output is correct |
25 |
Correct |
362 ms |
15468 KB |
Output is correct |
26 |
Correct |
311 ms |
17236 KB |
Output is correct |
27 |
Execution timed out |
5099 ms |
23840 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |