#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
vector<vector<int>> graf, auxgraf;
int p, n, m, v1[300005], v2[300005], c, cycle1, cycle2;
int dfs1(int node)
{
if(!v1[node])
return 0;
if(v1[node] > 0)
return v1[node];
if(graf[node].size())
{
v1[node] = 0;
v1[node] = dfs1(graf[node][0]);
if(v1[node] > 0)
v1[node]++;
return v1[node];
}
return 0;
}
int dfs2(int node)
{
if(!v2[node])
return 0;
if(v2[node] > 0)
return v2[node];
if(graf[node].size())
{
v2[node] = 0;
v2[node] = dfs2(graf[node][0]);
if(v2[node] > 0)
v2[node]++;
return v2[node];
}
return 0;
}
int dfs3(int nodeStart)
{
int dist = 0, node;
stack<int> s;
s.push(nodeStart);
v1[nodeStart] = 1;
while(!s.empty())
{
node = s.top();
s.pop();
v1[node] = 1;
if(!graf[node].size())
return 0;
if(graf[node][0] == nodeStart)
return dist + 2;
dist++;
if(!v1[graf[node][0]])
s.push(graf[node][0]);
}
return 0;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
p = P;
n = N;
m = M;
graf.resize(2 * N + 1);
auxgraf.resize(N + 1);
for(int i = 0; i < 2 * N; i++)
v2[i] = -1;
for(int i = 0; i < M; i++)
{
if(auxgraf[R[i][0]].size() < 2)
auxgraf[R[i][0]].push_back(R[i][1]);
if(auxgraf[R[i][1]].size() < 2)
auxgraf[R[i][1]].push_back(R[i][0]);
}
for(int i = 0; i < N; i++)
{
if(auxgraf[auxgraf[i][0]][0] == i && auxgraf[auxgraf[i][0]].size() > 1)
graf[2 * i].push_back(2 * auxgraf[i][0] + 1);
else
graf[2 * i].push_back(2 * auxgraf[i][0]);
if(auxgraf[i].size() == 2)
{
if(auxgraf[auxgraf[i][1]][0] == i && auxgraf[auxgraf[i][1]].size() > 1)
graf[2 * i + 1].push_back(2 * auxgraf[i][1] + 1);
else
graf[2 * i + 1].push_back(2 * auxgraf[i][1]);
}
}
cycle1 = dfs3(P * 2);
for(int i = 0; i < 2 * N; i++)
v1[i] = 0;
cycle2 = dfs3(P * 2 + 1);
for(int i = 0; i < 2 * N; i++)
v1[i] = -1;
v1[P * 2] = 1;
for(int i = 0; i < 2 * N; i += 2)
{
if(v1[i])
v1[i] = dfs1(i);
}
v2[P * 2 + 1] = 1;
for(int i = 0; i < 2 * N; i += 2)
{
if(v2[i])
v2[i] = dfs2(i);
}
for(int i = 0; i < Q; i++)
{
c = 0;
for(int j = 0; j < 2 * N; j += 2)
{
if(!cycle1 && G[i] - v1[j] + 1 == 0)
c++;
else if(!cycle2 && G[i] - v2[j] + 1 == 0)
c++;
else if(cycle1 && (G[i] - v1[j] + 1) % cycle1 == 0)
c++;
else if(cycle2 && (G[i] - v2[j] + 1) % cycle2 == 0)
c++;
}
answer(c);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
