Submission #5074

#	Time	Username	Problem	Language	Result	Execution time	Memory
5074		cki86201	Tropical Garden (IOI11_garden)	C++98	69 / 100	5041 ms	75412 KiB

garden

#include "garden.h"
#include "gardenlib.h"

//for 69 point;

const int N_ = 150020;

int nxt[N_][2];
int up[N_][2][31][2];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	int i, j, k;
	++P;
	for(i=0;i<M;i++)R[i][0]++, R[i][1]++;
	for(i=0;i<M;i++){
		if(!nxt[R[i][0]][0])nxt[R[i][0]][0] = R[i][1];
		else if(!nxt[R[i][0]][1])nxt[R[i][0]][1] = R[i][1];
		if(!nxt[R[i][1]][0])nxt[R[i][1]][0] = R[i][0];
		else if(!nxt[R[i][1]][1])nxt[R[i][1]][1] = R[i][0];
	}
	for(i=1;i<=N;i++)
		for(j=0;j<2;j++){
			up[i][j][0][1] = nxt[i][j];
			if(nxt[nxt[i][j]][0] == i && nxt[nxt[i][j]][1])up[i][j][0][0] = 1;
		}
	for(k=1;k<31;k++)
		for(i=1;i<=N;i++)
			for(j=0;j<2;j++){
				int t = up[i][j][k-1][0];
				up[i][j][k][0] = up[up[i][j][k-1][1]][t][k-1][0];
				up[i][j][k][1] = up[up[i][j][k-1][1]][t][k-1][1];
			}
	for(i=0;i<Q;i++){
		int cnt = 0;
		for(j=1;j<=N;j++){
			int now = j, to = 0;
			for(int k=30;k>=0;k--){
				if(1<<k&G[i]){
					int save = now;
					now = up[now][to][k][1];
					to = up[save][to][k][0];
				}
			}
			if(now == P)cnt++;
		}
		answer(cnt);
	}
}

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