#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
vector <pair <int, int>> dgraf[1000005];
int parent[1000005];
vector <int> graf[1000005];
bool resenje[1000005];
bool cmp(pair <int, int> a, pair <int, int> b){
return a.second < b.second;
}
int n, m, p, q;
int depth[1000005];
int cycle_size[1000005];
bool visited[1000005];
void dfs(int v){
visited[v] = 1;
//cout << "dfs " << v << " " << parent[v] << endl;
for(auto c : graf[v]){
if(visited[c]){
//cout << "u jbt\n";
//cout << c << " " << v << endl;
int x = v;
queue <int> q;
while(x != c){
q.push(x);
x = parent[x];
if(x == c) break;
//cout << x << " " << c << endl;
}
q.push(c);
int g = q.size();
while(!q.empty()){
cycle_size[q.front()] = g;
q.pop();
}
}
else{
depth[c] = depth[v] + 1;
dfs(c);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n = N, m = M, p = P, q = Q;
for(int i=0; i<m; i++){
dgraf[R[i][0]].push_back({R[i][1], i});
dgraf[R[i][1]].push_back({R[i][0], i});
}
for(int i=0; i<n; i++){
sort(dgraf[i].begin(), dgraf[i].end(), cmp);
}
for(int i=0; i<n; i++){
if(dgraf[i].size() == 1){
if(dgraf[dgraf[i][0].first][0].first == i){
parent[i] = dgraf[i][0].first + n;
parent[i+n] = dgraf[i][0].first + n;
}
else{
parent[i] = dgraf[i][0].first;
parent[i+n] = dgraf[i][0].first;
}
}
else{
if(dgraf[dgraf[i][0].first][0].first == i) parent[i] = dgraf[i][0].first + n;
else parent[i] = dgraf[i][0].first;
if(dgraf[dgraf[i][1].first][0].first == i) parent[i+n] = dgraf[i][1].first + n;
else parent[i+n] = dgraf[i][1].first;
}
}
for(int i=0; i<2*n; i++){
//cout << i << "<-" << parent[i] << "\n";
graf[parent[i]].push_back(i);
}
//return;
for(int query=0; query<q; query++){
int k = G[query];
int cnt = 0;
for(int i=0; i<2*n; i++){
visited[i] = 0;
depth[i] = -1;
resenje[i] = 0;
}
depth[p] = 0;
dfs(p);
for(int i=0; i<n; i++){
if(depth[i] == -1) continue;
//cout << i << " depth " << depth[i] << endl;
if(depth[i] == k){
resenje[i] = 1;
}
else if(cycle_size[p]){
if(k > depth[i] && (k-depth[i])%cycle_size[p] == 0){
resenje[i] = 1;
}
}
}
for(int i=n; i<2*n; i++){
if(dgraf[i-n].size() != 1){
//cout << n-i << endl;
continue;
}
if(depth[i] == -1) continue;
if(depth[i] == k){
resenje[i-k] = 1;
}
else if(cycle_size[p]){
if(k > depth[i] && (k-depth[i])%cycle_size[p] == 0){
resenje[i-k] = 1;
}
}
}
/*for(int i=0; i<n; i++){
cout << i << " resenje " << resenje[i] << endl;
}*/
for(int i=0; i<2*n; i++){
visited[i] = 0;
depth[i] = -1;
}
depth[p+n] = 0;
dfs(p+n);
for(int i=0; i<n; i++){
//cout << i << " depth " << depth[i] << endl;
if(depth[i] == -1) continue;
if(depth[i] == k){
resenje[i] = 1;
}
else if(cycle_size[p+n]){
if(k > depth[i] && (k-depth[i])%cycle_size[p+n] == 0){
resenje[i] = 1;
}
}
}
for(int i=n; i<2*n; i++){
if(dgraf[i-n].size() != 1){
//cout << n-i << endl;
continue;
}
if(depth[i] == -1) continue;
if(depth[i] == k){
resenje[i-n] = 1;
}
else if(cycle_size[p+n]){
//cout << depth[i] << " fg " << cycle_size[i] << endl;
if(k > depth[i] && (k-depth[i])%cycle_size[p+n] == 0){
resenje[i-n] = 1;
}
}
}
for(int i=0; i<n; i++){
//cout << i << " resenje " << resenje[i] << endl;
cnt += resenje[i];
}
//cout << cnt << " je resenje\n";
answer(cnt);
}
return;
}
/*
2
1 0
0 1
5
1 2 3 4 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
47608 KB |
Output is correct |
| 2 |
Correct |
45 ms |
47480 KB |
Output is correct |
| 3 |
Correct |
44 ms |
47480 KB |
Output is correct |
| 4 |
Correct |
55 ms |
47352 KB |
Output is correct |
| 5 |
Correct |
44 ms |
47352 KB |
Output is correct |
| 6 |
Correct |
46 ms |
47816 KB |
Output is correct |
| 7 |
Correct |
55 ms |
47352 KB |
Output is correct |
| 8 |
Correct |
60 ms |
47452 KB |
Output is correct |
| 9 |
Correct |
47 ms |
47708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
47608 KB |
Output is correct |
| 2 |
Correct |
45 ms |
47480 KB |
Output is correct |
| 3 |
Correct |
44 ms |
47480 KB |
Output is correct |
| 4 |
Correct |
55 ms |
47352 KB |
Output is correct |
| 5 |
Correct |
44 ms |
47352 KB |
Output is correct |
| 6 |
Correct |
46 ms |
47816 KB |
Output is correct |
| 7 |
Correct |
55 ms |
47352 KB |
Output is correct |
| 8 |
Correct |
60 ms |
47452 KB |
Output is correct |
| 9 |
Correct |
47 ms |
47708 KB |
Output is correct |
| 10 |
Correct |
48 ms |
47300 KB |
Output is correct |
| 11 |
Correct |
60 ms |
49944 KB |
Output is correct |
| 12 |
Correct |
82 ms |
51560 KB |
Output is correct |
| 13 |
Correct |
129 ms |
85724 KB |
Output is correct |
| 14 |
Runtime error |
236 ms |
122900 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
47608 KB |
Output is correct |
| 2 |
Correct |
45 ms |
47480 KB |
Output is correct |
| 3 |
Correct |
44 ms |
47480 KB |
Output is correct |
| 4 |
Correct |
55 ms |
47352 KB |
Output is correct |
| 5 |
Correct |
44 ms |
47352 KB |
Output is correct |
| 6 |
Correct |
46 ms |
47816 KB |
Output is correct |
| 7 |
Correct |
55 ms |
47352 KB |
Output is correct |
| 8 |
Correct |
60 ms |
47452 KB |
Output is correct |
| 9 |
Correct |
47 ms |
47708 KB |
Output is correct |
| 10 |
Correct |
48 ms |
47300 KB |
Output is correct |
| 11 |
Correct |
60 ms |
49944 KB |
Output is correct |
| 12 |
Correct |
82 ms |
51560 KB |
Output is correct |
| 13 |
Correct |
129 ms |
85724 KB |
Output is correct |
| 14 |
Runtime error |
236 ms |
122900 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
