제출 #88007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88007		Pajaraja	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	4054 ms	36788 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> h[150007],g[300007];
int d[2][300007],nxt[300007];
void dfs(int s,int k,int di)
{
	if(d[k][s]!=-1)
	{
		d[k][s]=di;
		return;
	}
	d[k][s]=di;
	for(int i=0;i<g[s].size();i++) dfs(g[s][i],k,di+1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	int n=N;
    for(int i=0;i<M;i++)
    {
    	int p;
    	p=R[i][1];
    	h[R[i][0]].push_back(p);
    	p=R[i][0];
        h[R[i][1]].push_back(p);
	}
	for(int i=0;i<N;i++)
	{
		if(h[h[i][0]][0]==i) nxt[i]=h[i][0]+n;
		else nxt[i]=h[i][0];
		if(h[i].size()>1)
		{
		    if(h[h[i][1]][0]==i) nxt[i+n]=h[i][1]+n;
		    else nxt[i+n]=h[i][1];
		}
		else
		{
			if(h[h[i][0]][0]==i) nxt[i+n]=h[i][0]+n;
		    else nxt[i+n]=h[i][0];
		}
		d[0][i]=d[0][i+n]=d[1][i]=d[1][i+n]=-1;
	}
	for(int i=0;i<2*n;i++) g[nxt[i]].push_back(i);
	dfs(P,0,0);
	dfs(P+n,1,0);
	for(int j=0;j<Q;j++)
	{
		int sol=0;
	    for(int i=0;i<N;i++) if(d[0][i]==G[j] || (d[0][i]>0 && d[0][P]>0 && d[0][i]<=G[j] && d[0][i]%d[0][P]==G[j]%d[0][P]) || d[1][i]==G[j] || (d[1][i]>0 && d[1][P+n]>0 && d[1][i]<=G[j] && d[1][i]%d[1][P+n]==G[j] % d[1][P+n])) sol++;
		answer(sol);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) dfs(g[s][i],k,di+1);
              ~^~~~~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31