이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <assert.h>
#include <iostream>
#include <algorithm>
#define vi vector<int>
const int INF = 1e9;
using namespace std;
vi sadj[150001], adj[300001];
int dst[2][300001], cyc[2];
vi ans[2][300001];
void DFS(int u, int id)
{
// cout << u << " " << id << " " << dst[id][u] << "\n";
for (auto v : adj[u])
{
if (dst[id][v] == INF)
{
dst[id][v] = dst[id][u] + 1;
DFS(v, id);
}
else
{
assert(cyc[id] == -1 && dst[id][v] == 0);
cyc[id] = dst[id][u] + 1;
}
}
}
/*
It is possible to represent the problem as a digraph with 2N nodes
such that each node has at most one outgoing edge.
We can use this property to determine which cycle lengths are valid.
*/
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for (int i = 0; i < M; i++)
{
sadj[R[i][0]].push_back(R[i][1]);
sadj[R[i][1]].push_back(R[i][0]);
}
cyc[0] = cyc[1] = -1;
for (int u = 0; u < N; u++)
{
for (int j = 0; j < min(2, (int)sadj[u].size()); j++)
{
int v = sadj[u][j];
//cout << "Add edge " << 2 * u + j << " -> " << 2 * v + (sadj[v].size() > 1 && u == sadj[v][0]) << "\n";
adj[2 * v + (sadj[v].size() > 1 && u == sadj[v][0])].push_back(2 * u + j);
}
}
for (int i = 0; i < 2 * N; i++) {dst[0][i] = dst[1][i] = INF;}
for (int i = 0; i < 2; i++)
{
dst[i][2 * P + i] = 0;
DFS(2 * P + i, i);
if (cyc[i] == -1)
{
for (int j = 0; j < 2 * N; j += 2)
{
if (dst[i][j] < INF) ans[i][0].push_back(dst[i][j]);
}
sort(ans[i][0].begin(), ans[i][0].end());
}
else
{
for (int j = 0; j < 2 * N; j += 2)
{
if (dst[i][j] < INF) ans[i][dst[i][j] % cyc[i]].push_back(dst[i][j]);
}
for (int j = 0; j < cyc[i]; j++)
{
sort(ans[i][j].begin(), ans[i][j].end());
}
}
}
for (int i = 0; i < Q; i++)
{
int ret = 0;
for (int j = 0; j < 2; j++)
{
if (cyc[j] == -1)
{
ret += upper_bound(ans[j][0].begin(), ans[j][0].end(), G[i]) - lower_bound(ans[j][0].begin(), ans[j][0].end(), G[i]);
}
else
{
int v = G[i] % cyc[j];
ret += upper_bound(ans[j][v].begin(), ans[j][v].end(), G[i]) - ans[j][v].begin();
}
}
answer(ret);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |