# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
60793 | Vahan | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++17 | 2871 ms | 46232 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "garden.h"
#include "gardenlib.h"
#include<vector>
#include<iostream>
using namespace std;
int p,u[400000],u1[400000],u2[400000],l1[400000],l2[400000];
int a[400000];
const int MAXN=400000;
vector<int> g[400005],inv[400000];
int dfs1(int v)
{
if(v==2*p)
return 1;
if(u[v]==1)
return -MAXN;
u[v]=1;
return dfs1(a[v])+1;
}
int dfs2(int v)
{
if(v==2*p+1)
return 1;
if(u[v]==1)
return -MAXN;
u[v]=1;
return dfs2(a[v])+1;
}
void dfs11(int v,int h)
{
if(u1[v]==1)
return;
u1[v]=1;
l1[v]=h;
for(int i=0;i<inv[v].size();i++)
{
int to=inv[v][i];
dfs11(to,h+1);
}
}
void dfs22(int v,int h)
{
if(u2[v]==1)
return;
u2[v]=1;
l2[v]=h;
for(int i=0;i<inv[v].size();i++)
{
int to=inv[v][i];
dfs22(to,h+1);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
p=P;
for(int i=0;i<M;i++)
{
g[R[i][0]].push_back(R[i][1]);
g[R[i][1]].push_back(R[i][0]);
}
for(int i=0;i<N;i++)
{
if(g[i].size()==1)
{
if(g[g[i][0]][0]==i)
a[2*i+1]=2*g[i][0]+1;
else
a[2*i+1]=2*g[i][0];
a[2*i]=a[2*i+1];
}
else
{
if(g[g[i][0]][0]==i)
a[2*i]=2*g[i][0]+1;
else
a[2*i]=2*g[i][0];
if(g[g[i][1]][0]==i)
a[2*i+1]=2*g[i][1]+1;
else
a[2*i+1]=2*g[i][1];
}
}
for(int i=0;i<2*N;i++)
{
inv[a[i]].push_back(i);
l1[i]=-1;
l2[i]=-1;
}
int r1=dfs1(a[2*P]);
if(r1<0)
r1=0;
for(int i=0;i<2*N;i++)
u[i]=0;
int r2=dfs2(a[2*P+1]);
if(r2<0)
r2=0;
dfs11(2*p,0);
dfs22(2*p+1,0);
for(int i=0;i<Q;i++)
{
int an=0;
for(int j=0;j<N;j++)
{
if(r1==0 && G[i]==l1[2*j])
an++;
else if(r1>0 && G[i]-l1[2*j]>=0 && (G[i]-l1[2*j])%r1==0 && l1[2*j]!=-1)
an++;
else if(r2==0 && G[i]==l2[2*j])
an++;
else if(r2>0 && G[i]-l2[2*j]>=0 && (G[i]-l2[2*j])%r2==0 && l2[2*j]!=-1)
an++;
}
answer(an);
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |