void answer(int x);
//#include "garden.h"
//#include "gardenlib.h"
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;
vector<pi> graph0[150005];
vector<int> graph1[300005];
vector<int> proc;
int nxt[300005];
int low[150005];
int periods[300005];
int deg[300005];
int n, qcnt;
int *g;
queue<int> q, p, d;
bool vis[300005];
void get_periods(){
for (int i=0; i<2*n; i++) {
if(deg[i] == 1){
q.push(i);
}
}
while (!q.empty()) {
int qf = q.front();
q.pop();
deg[qf] = 0;
for (auto &i : graph1[qf]){
deg[i]--;
if(deg[i] == 1){
q.push(i);
}
}
}
for (int i=0; i<2*n; i++) {
if(deg[i] != 0){
proc.clear();
q.push(i);
int cnt = 0;
while (!q.empty()) {
int qf = q.front();
q.pop();
deg[qf] = 0;
cnt++;
proc.push_back(qf);
for (auto &i : graph1[qf]){
if(deg[i] != 0){
deg[i] = 0;
q.push(i);
}
}
if(deg[nxt[qf]] != 0){
deg[nxt[qf]] = 0;
q.push(nxt[qf]);
}
}
for (auto &i : proc){
periods[i] = cnt;
}
}
}
// for (int i=0; i<2*n; i++) {
// printf("%d %d\n",i, periods[i]);
//}
}
bool cnt[150005];
void solve(int st, int g){ // st 점에서 G[i] 번 방문해서 도달하는 점의 개수 추가
memset(vis,0,sizeof(vis));
q.push(st);
p.push(-1);
d.push(0);
vis[st] = 1;
while (!q.empty()) {
int qf = q.front(), pf = p.front(), df = d.front();
q.pop(), p.pop(), d.pop();
pf = max(pf, periods[qf]);
if(qf % 2 == 0){
//for (int i=0; i<N; i++) {
if(pf == -1){
if(df == g){
cnt[qf / 2] = 1;
// printf("%d %d\n",i,qf/2);
}
}
else{
if(df <= g && g % pf == df % pf){
cnt[qf / 2] = 1;
// printf("%d %d\n",i,qf/2);
}
}
// }
}
for (auto &i : graph1[qf]){
if(vis[i]) continue;
vis[i] = 1;
q.push(i);
p.push(pf);
d.push(df + 1);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N, qcnt = Q, g = G;
memset(periods,-1,sizeof(periods));
memset(low,0x3f,sizeof(low));
for (int i=0; i<M; i++) {
for (int j=0; j<2; j++) {
low[R[i][j]] = min(low[R[i][j]],i);
}
graph0[R[i][0]].push_back(pi(R[i][1],i));
graph0[R[i][1]].push_back(pi(R[i][0],i));
}
for (int i=0; i<N; i++) {
if(low[graph0[i][0].first] == graph0[i][0].second){
nxt[2*i] = graph0[i][0].first * 2 + 1;
}
else{
nxt[2*i] = graph0[i][0].first * 2;
}
if(graph0[i].size() == 1){
nxt[2*i+1] = nxt[2*i];
}
else{
if(low[graph0[i][1].first] == graph0[i][1].second){
nxt[2*i+1] = graph0[i][1].first * 2 + 1;
}
else{
nxt[2*i+1] = graph0[i][1].first * 2;
}
}
}
for (int i=0; i<2*N; i++){
// printf("%d %d\n",i,nxt[i]);
graph1[nxt[i]].push_back(i);
deg[i]++;
deg[nxt[i]]++;
}
get_periods();
for (int i=0; i<Q; i++) {
memset(cnt,0,sizeof(cnt));
solve(2*P,G[i]);
solve(2*P+1,G[i]);
int ret = 0;
for (int j=0; j<N; j++) {
if(cnt[j]) ret++;
}
answer(ret);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
13176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
13176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
13176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
