Submission #348987

#	Time	Username	Problem	Language	Result	Execution time	Memory
348987		Mefarnis	Tropical Garden (IOI11_garden)	C++14	49 / 100	40 ms	47212 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define maxk 18
#define maxn 150003
#define pb push_back
using namespace std;

int n;
int dp[maxn][2][maxk][2];
vector<int> adj[maxn];

void precalc() {
	memset(dp,-1,sizeof(dp));
	for( int u = 0 ; u < n ; u++ ) {
		int v = adj[u][0];
		dp[u][1][0][0] = v;
		if(adj[v].size() == 1)
			dp[u][1][0][1] = 1;
		else
			dp[u][1][0][1] = (adj[v][0] != u);
		if(adj[u].size() == 2) {
			v = adj[u][1];
			dp[u][0][0][0] = v;
			if(adj[v].size() == 1)
				dp[u][0][0][1] = 1;
			else
				dp[u][0][0][1] = (adj[v][0] != u);
		}
	}
	for( int k = 1 ; k < maxk ; k++ )
		for( int u = 0 ; u < n ; u++ )
			for( int st = 0 ; st < 2 ; st++ )
				if(dp[u][st][k-1][0] != -1) {
					int v = dp[u][st][k-1][0];
					int st2 = dp[u][st][k-1][1];
					dp[u][st][k][0] = dp[v][st2][k-1][0];
					dp[u][st][k][1] = dp[v][st2][k-1][1];
				}
}

int solve(int u , int d) {
	int st = 1;
	for( int i = maxk-1 ; i >= 0 ; i-- )
		if(d & (1<<i)) {
			int v = dp[u][st][i][0];
			int stv = dp[u][st][i][1];
			u = v;
			st = stv;
		}
	return u;
}

void count_routes(int N, int m, int p, int e[][2], int q, int dist[]) {
	n = N;
	for( int i = 0 ; i < m ; i++ ) {
		int u = e[i][0];
		int v = e[i][1];
		if(adj[u].size() < 2)
			adj[u].pb(v);
		if(adj[v].size() < 2)
			adj[v].pb(u);
	}
	precalc();
	for( int tc = 0 ; tc < q ; tc++ ) {
		int d = dist[tc] , ans = 0;
		for( int i = 0 ; i < n ; i++ )
			ans += (solve(i,d) == p);
		answer(ans);
	}
}

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