Submission #898708

#	Time	Username	Problem	Language	Result	Execution time	Memory
898708		Jawad_Akbar_JJ	Tropical Garden (IOI11_garden)	C++17	0 / 100	1 ms	6744 KiB

garden

#include <iostream>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

const int NN = 1.5e5 + 10;

int best[NN][3];
int dp[NN][32][2][2];

void count_routes(int n,int m,int p,int r[][2],int q,int g[]){
	
	for (int i=1;i<=n;i++)
		best[i][0] = best[i][1] = -1;

	for (int i=0;i<m;i++){
		int u = r[i][0] + 1;
		int v = r[i][1] + 1;
		if (best[u][0] == -1)
			best[u][0] = v;
		else if (best[u][1] == -1)
			best[u][1] = v;

		if (best[v][0] == -1)
			best[v][0] = u;
		else if (best[v][1] == -1)
			best[v][1] = u;
	}

	for (int i=1;i<=n;i++)
		if (best[i][1] == -1)
			best[i][1] = best[i][0];


	for (int i=1;i<=n;i++){
		int v = best[i][0];
		if (best[v][0]==i)
			dp[i][0][1][1] = v;
		else
			dp[i][0][1][0] = v;

		int u = best[i][1];
		if (best[u][0]==i)
			dp[i][0][0][1] = u;
		else
			dp[i][0][0][0] = u;
	}

	for (int j=1;j<=1;j++)
		for (int i=1;i<=n;i++)
			for (int k=0;k<2;k++)
				for (int l=0;l<2;l++)
					for (int lp=0;lp<2;lp++){
						int v = dp[i][j-1][k][l];
						if (v==0 or dp[v][j-1][1-l][lp]==0)
							continue;
						dp[i][j][k][lp] = dp[v][j-1][1-l][lp];
					}
		

	p++;

	for (int j=0;j<q;j++){
		int ans = 0;
		for (int i=1;i<=n;i++){
			int cur = i;
			int d = 1;

			for (int k=29;k>=0;k--){
				if (((1<<k)&g[j])==0)
					continue;
				if (dp[cur][k][d][0]==0)
					cur = dp[cur][k][d][1],d = 0;
				else
					cur = dp[cur][k][d][0],d = 1;
			}
			if (cur == p)
				ans++;
		}
		answer(ans);
	}
}

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