#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int n = N, m = M;
typedef pair<int,int> ii;
ii beautiful[N];
fill(beautiful,beautiful+N,ii(-1,-1));
for(int i = 0;i < m;i++){
int a = R[i][0];
int b = R[i][1];
if(beautiful[a].first == -1) beautiful[a].first = b;
else if(beautiful[a].second == -1) beautiful[a].second = b;
if(beautiful[b].first == -1) beautiful[b].first = a;
else if(beautiful[b].second == -1) beautiful[b].second = a;
}
for(int i = 0;i < n;i++){
if(beautiful[i].second == -1) beautiful[i].second = beautiful[i].first;
//cout << beautiful[i].first << " " << beautiful[i].second << "\n";
}
int big = 1000000000;
int dis[2*n];
int reach[2*n];
fill(dis,dis+2*n,-1);
fill(reach,reach+2*n,-1);
dis[P] = 0;
dis[P+N] = 0;
reach[P] = 1;
reach[P+N] = 2;
for(int i = 0;i < 2 * n;i++){
int a = i;
set<int> vis;
stack<int> order;
while(true){
//cout << a << " ";
if(dis[a] != -1){
int c = 1;
while(!order.empty()){
dis[order.top()] = dis[a] + c;
reach[order.top()] = reach[a];
order.pop();
c++;
}
break;
}
else if(vis.find(a) != vis.end()){
while(!order.empty()){
dis[order.top()] = big + 7;
reach[order.top()] = 0;
order.pop();
}
}
vis.insert(a);
order.push(a);
int b;
if(a < n){
b = beautiful[a].first;
}
else{
a -= n;
b = beautiful[a].second;
}
if(beautiful[b].first == a){
b += n;
}
a = b;
}
//cout << "\n";
}
for(int i = 0;i < 2 * n;i++){
//cout << dis[i] << " ";
}
ii ptowhere;
ii nptowhere;
int a = P;
set<int> vis;
while(true){
if(a == P + N){
ptowhere = ii(2,vis.size());
break;
}
if(vis.find(a) != vis.end()){
if(a == P){
ptowhere = ii(1,vis.size());
}
else{
ptowhere = ii(0,-1);
}
break;
}
vis.insert(a);
int b;
if(a < n){
b = beautiful[a].first;
}
else{
a -= n;
b = beautiful[a].second;
}
if(beautiful[b].first == a){
b += n;
}
a = b;
}
a = P+N;
vis.clear();
while(true){
if(a == P){
nptowhere = ii(1,vis.size());
break;
}
if(vis.find(a) != vis.end()){
if(a == P + N){
nptowhere = ii(2,vis.size());
}
else{
nptowhere = ii(0,-1);
}
break;
}
vis.insert(a);
int b;
if(a < n){
b = beautiful[a].first;
}
else{
a -= n;
b = beautiful[a].second;
}
if(beautiful[b].first == a){
b += n;
}
a = b;
}
//cout << ptowhere.first << " " << ptowhere.second << " " << nptowhere.first << " " << nptowhere.second;
if(ptowhere.first == 2 && nptowhere.first == 1){
for(int qq = 0;qq < Q;qq++){
int x = G[qq];
int ans = 0;
for(int i = 0;i < n;i++){
if(x - dis[i] >= 0 && (x - dis[i]) % (ptowhere.second + nptowhere.second) == 0){
ans++;
continue;
}
if(reach[i] == 1){
if((x - dis[i] - ptowhere.second) >= 0 && (x - dis[i] - ptowhere.second) % (ptowhere.second + nptowhere.second) == 0){
ans++;
continue;
}
}
else if(reach[i] == 2){
if((x - dis[i] - nptowhere.second) >= 0 && (x - dis[i] - nptowhere.second) % (ptowhere.second + nptowhere.second) == 0){
ans++;
continue;
}
}
}
answer(ans);
}
}
else{
for(int qq = 0;qq < Q;qq++){
int x = G[qq];
int ans = 0;
for(int i = 0;i < n;i++){
if(reach[i] == 1){
if(dis[i] == x){
ans++;
continue;
}
if(ptowhere.first == 1){
if(x - dis[i] >= 0 && (x-dis[i]) % ptowhere.second == 0){
ans++;
continue;
}
}
else if(ptowhere.first == 2){
if(nptowhere.first == 0){
if(dis[i] + ptowhere.second == x){
ans++;
continue;
}
}
else if(nptowhere.first == 2){
if((x - dis[i] - ptowhere.second) >= 0 && (x - dis[i] - ptowhere.second) % nptowhere.second == 0){
ans++;
assert(false);
continue;
}
}
}
}
else if(reach[i] == 2){
if(dis[i] == x){
ans++;
continue;
}
if(nptowhere.first == 2){
if(x - dis[i] >= 0 && (x-dis[i]) % nptowhere.second == 0){
ans++;
continue;
}
}
else if(nptowhere.first == 1){
if(ptowhere.first == 0){
if(dis[i] + nptowhere.second == x){
ans++;
continue;
}
}
else if(ptowhere.first == 2){
if((x-dis[i]-nptowhere.second) >= 0 && (x-dis[i]-nptowhere.second) % ptowhere.second == 0){
ans++;
continue;
}
}
}
}
}
answer(ans);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
380 KB |
Output is correct |
| 7 |
Correct |
2 ms |
420 KB |
Output is correct |
| 8 |
Correct |
2 ms |
296 KB |
Output is correct |
| 9 |
Correct |
4 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
380 KB |
Output is correct |
| 7 |
Correct |
2 ms |
420 KB |
Output is correct |
| 8 |
Correct |
2 ms |
296 KB |
Output is correct |
| 9 |
Correct |
4 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
380 KB |
Output is correct |
| 11 |
Correct |
16 ms |
1232 KB |
Output is correct |
| 12 |
Correct |
33 ms |
1912 KB |
Output is correct |
| 13 |
Correct |
110 ms |
10984 KB |
Output is correct |
| 14 |
Correct |
92 ms |
4692 KB |
Output is correct |
| 15 |
Correct |
93 ms |
4748 KB |
Output is correct |
| 16 |
Correct |
74 ms |
3704 KB |
Output is correct |
| 17 |
Runtime error |
70 ms |
6392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
380 KB |
Output is correct |
| 7 |
Correct |
2 ms |
420 KB |
Output is correct |
| 8 |
Correct |
2 ms |
296 KB |
Output is correct |
| 9 |
Correct |
4 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
380 KB |
Output is correct |
| 11 |
Correct |
16 ms |
1232 KB |
Output is correct |
| 12 |
Correct |
33 ms |
1912 KB |
Output is correct |
| 13 |
Correct |
110 ms |
10984 KB |
Output is correct |
| 14 |
Correct |
92 ms |
4692 KB |
Output is correct |
| 15 |
Correct |
93 ms |
4748 KB |
Output is correct |
| 16 |
Correct |
74 ms |
3704 KB |
Output is correct |
| 17 |
Runtime error |
70 ms |
6392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Halted |
0 ms |
0 KB |
- |
