#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
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][2];
int cycle_size[1000005][2];
bool visited[1000005][2];
void dfs(int v, int koji){
visited[v][koji] = 1;
for(auto c : graf[v]){
if(visited[c][koji]){
int x = v;
queue <int> q;
while(x != c){
q.push(x);
x = parent[x];
if(x == c) break;
}
q.push(c);
int g = q.size();
while(!q.empty()){
cycle_size[q.front()][koji] = g;
q.pop();
}
}
else{
depth[c][koji] = depth[v][koji] + 1;
dfs(c, koji);
}
}
}
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++){
graf[parent[i]].push_back(i);
}
for(int i=0; i<2*n; i++){
depth[i][0] = depth[i][1] = -1;
cycle_size[i][0] = cycle_size[i][1] = 0;
}
depth[p][0] = 0;
dfs(p, 0);
depth[p+n][1] = 0;
dfs(p+n, 1);
for(int query=0; query<q; query++){
int k = G[query];
int cnt = 0;
for(int i=0; i<n; i++) resenje[i] = 0;
for(int i=0; i<n; i++){
if(depth[i][0] == -1) continue;
if(depth[i][0] == k){
resenje[i] = 1;
}
else if(cycle_size[p][0]){
if(k > depth[i][0] && (k-depth[i][0])%cycle_size[p][0] == 0){
resenje[i] = 1;
//cout << i << " e1 " << endl;
}
}
}
for(int i=n; i<2*n; i++){
if(dgraf[i-n].size() != 1){
continue;
}
if(depth[i][0] == INF) continue;
if(depth[i][0] == k){
resenje[i-n] = 1;
}
else if(cycle_size[p][0]){
if(k > depth[i][0] && (k-depth[i][0])%cycle_size[p][0] == 0){
resenje[i-n] = 1;
//cout << i << " e2 " << endl;
}
}
}
/// drugi
for(int i=0; i<n; i++){
if(depth[i][1] == -1) continue;
if(depth[i][1] == k){
resenje[i] = 1;
}
else if(cycle_size[p+n][1]){
if(k > depth[i][1] && (k-depth[i][1])%cycle_size[p+n][1] == 0){
//cout << i << " e3 " << endl;
resenje[i] = 1;
}
}
}
for(int i=n; i<2*n; i++){
if(dgraf[i-n].size() != 1){
continue;
}
if(depth[i][1] == -1) continue;
if(depth[i][1] == k){
resenje[i-n] = 1;
}
else if(cycle_size[p+n][1]){
if(k > depth[i][1] && (k-depth[i][1])%cycle_size[p+n][1] == 0){
resenje[i-n] = 1;
//cout << i << " e4 " << endl;
}
}
}
for(int i=0; i<n; i++){
cnt += resenje[i];
}
answer(cnt);
}
return;
}
/*
2
1 0
0 1
5
1 2 3 4 5
sdgfhsdfgdfgds
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
47736 KB |
Output is correct |
| 2 |
Correct |
45 ms |
47452 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
47580 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
47736 KB |
Output is correct |
| 2 |
Correct |
45 ms |
47452 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
47580 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
47736 KB |
Output is correct |
| 2 |
Correct |
45 ms |
47452 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
47580 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
