| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1107722 | laight | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "garden.h"
#include "gardenlib.h"
#define pb emplace_back
#include<bits/stdc++.h>
using namespace std;
vector<int>g[300005];
vector<int> g2(600005);
int jp=0;
vector<int>g_rev[600005];
bool cycle=false;
int c;
map<int,bool>vs;
bool vs1[600005],vs2[600005];
void dfs(int u,int cnt,int pp)
{
if(vs[u])
{
if(u==pp)
{
cycle = true;
c = cnt;
}
return ;
}
vs[u]=true;
assert((int) g2[u].size() <= 1);
dfs(g2[u],cnt+1,pp);
}
int cnt_ans1[600005];
int cnt_ans2[600005];
void dfs1(int u,int cnt)
{
if(vs1[u]) return ;
vs1[u] = true;
cnt_ans1[u] = cnt;
for(auto v:g_rev[u]) dfs1(v,cnt+1);
}
void dfs2(int u,int cnt)
{
if(vs2[u]) return ;
vs2[u] = true;
cnt_ans2[u] = cnt;
for(auto v:g_rev[u]) dfs2(v,cnt+1);
}
void count_routes(int n, int m, int p, int R[][2], int Q, int G[])
{
for(int i=0;i<m;i++)
{
if(g[R[i][0]].size()<=2) g[R[i][0]].pb(R[i][1]);
if(g[R[i][1]].size()<=2) g[R[i][1]].pb(R[i][0]);
}
for(int i=0;i<n;i++)
{
int v = g[i][0];
if(i==g[v][0]) {g2[i] = v+n; g_rev[g2[i]].pb(v+n);}
else {g2[i] = v; g_rev[g2[i]].pb(v);}
int vv;
if(g[i].size()!=1) vv = g[i][1];
else vv = g[i][0];
if(i==g[vv][0]) {g2[i+n] = vv+n; g_rev[vv+n].pb(i+n);}
else {g2[i+n] = vv; g2[vv] = i+n;}
}
for(int i=0;i<2*n;i++)
{
g_rev[g2[i][0]].pb(i);
}
dfs(p,0,p);
bool cycle1 = cycle;
int c1 = c;
cycle=false;
vs.clear();
dfs(n+p,0,n+p);
vs.clear();
bool cycle2 = cycle;
int c2 = c;
dfs1(p,0);
dfs2(p+n,0);
for(int k=0;k<Q;k++)
{
int d = G[k];
int ans=0;
for(int i=0;i<n;i++)
{
bool ok = 0;
int len = d - cnt_ans1[i];
if(len >= 0 and vs1[i]) {
if(cycle1 and len%c1 == 0) ok = 1;
else if(!cycle1 and len == 0) ok = 1;
}
len = d - cnt_ans2[i];
if(len >= 0 and vs2[i]) {
if(cycle2 and len%c2 == 0) ok = 1;
else if(!cycle2 and len == 0) ok = 1;
}
ans += ok;
}
// cout << endl;
answer(ans);
}
}