#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
void dfs(int st, int dep, vector<int>(&g)[], int f[], bool vis[], int t, int p, int n){
vis[st]=1;
//cout << "visiting: " << st << endl;
f[st]=dep;
for(int i : g[st]){
if(i==t){
f[t]=dep+1;
}
if(vis[i])
continue;
if(i==st+n||i==st-n){
dfs(i,dep,g,f,vis,t, st, n);
continue;
}
dfs(i,dep+1,g,f,vis,t, st, n);
}
}
void count_routes(int n, int m, int t, int edges[][2], int q, int G[])
{
vector<int>g[2*n];
int cn[n];
fill(cn,cn+n,0);
for(int i = 0;i<m;i++){
int u1=edges[i][0];
int v1=edges[i][1];
//cout << u1 << " " << v1 << endl;
if(cn[u1]>cn[v1]){
swap(u1,v1);
}
int u2 = u1+n;
int v2 = v1+n;
if(cn[u1]==0&&cn[v1]==0){
// cout << "adding1: " << u1 << " " << v2 << endl;
// cout << "adding2: " << v1 << " " << u2 << endl;
g[v2].push_back(u1);
g[u2].push_back(v1);
}
else if(cn[u1]==0&&cn[v1]==1){
// cout << "adding3: " << u1 << " " << v1 << endl;
// cout << "adding4: " << v2 << " " << u2 << endl;
g[v1].push_back(u1);
g[u2].push_back(v2);
}
else if(cn[u1]==0&&cn[v1]>1){
// cout << "adding5: " << u1 << " " << v1 << endl;
g[v1].push_back(u1);
}
else if(cn[u1]==1&&cn[v1]==1){
//cout << "adding6: " << u2 << " " << v1 << endl;
//cout << "adding7: " << v2 << " " << u1 << endl;
g[v1].push_back(u2);
g[u1].push_back(v2);
}
else if(cn[u1]==1&&cn[v1]>1){
//cout << "adding8: " << u2 << " " << v1 << endl;;
g[v1].push_back(u2);
}
cn[u1]++;
cn[v1]++;
}
for(int i = 0;i<n;i++){
if(cn[i]==1){
g[i].push_back(i+n);
g[i+n].push_back(i);
}
}
int f1[2*n];
fill(f1,f1+2*n,-1);
bool vis[2*n];
fill(vis,vis+2*n,0);
//cout << "first: \n";
dfs(t,0,g,f1,vis,t,-1, n);
int f2[2*n];
fill(f2,f2+2*n,-1);
fill(vis,vis+2*n,0);
// cout << "second: \n";
dfs(t+n,0,g,f2,vis,t+n,-1, n);
for(int i = 0;i<q;i++){
int ans = 0;
// cout << "here" << endl;
// cout << "going in" << endl;
for(int j = 0;j<n;j++){
// cout << "inside loop now2" << endl;
//cout << i << " " << j << " " << t << " " << n << " " << f1[t] << " " << f1[j] << " " << f2[j] << " " << f2[t+n] <<endl;
if(f1[j]==G[i]||(f1[t]!=0&&f1[j]!=-1&&f1[j]<=G[i]&&f1[j]%f1[t]==G[i]%f1[t])){
ans++;
// cout << "added 1" << endl;
}
// cout << "outside first if" << endl;
else if(f2[j]==G[i]||(f2[t+n]!=0&&f2[j]!=-1&&f2[j]<=G[i]&&f2[j]%f2[t+n]==G[i]%f2[t+n])){
ans++;
// cout << "added 1 next" << endl;
}
}
//cout << "answering...";
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
