Submission #534943

#	Time	Username	Problem	Language	Result	Execution time	Memory
534943		shrimb	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	69 / 100	5039 ms	41976 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include"bits/stdc++.h"
using namespace std;

int nxt[150001][2];
int dp[150001][2][32];


void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	for (int i = 0 ; i < M ; i++) {
		auto [u, v] = R[i];
		u++, v++;
		if (!nxt[u][0] and !nxt[v][0]) {
			nxt[u][0] = -v;
			nxt[v][0] = -u;
		}
		if (!nxt[u][0]) nxt[u][0] = v;
		if (!nxt[v][0]) nxt[v][0] = u;

		if (abs(nxt[u][0]) != v and nxt[u][1] == 0) {
			if (abs(nxt[v][0]) == u) nxt[u][1] = -v;
			else nxt[u][1] = v;
		}

		if (abs(nxt[v][0]) != u and nxt[v][1] == 0) {
			if (abs(nxt[u][0]) == v) nxt[v][1] = -u;
			else nxt[v][1] = u;
		}
	}

	for (int i = 1 ; i <= N ; i++) {
		if (nxt[i][1] == 0) nxt[i][1] = nxt[i][0];
	}

	// for (int i = 1 ; i <= N ; i++) {
	// 	cout << i << ": " << nxt[i][0] << " " << nxt[i][1] << endl;
	// }

	for (int j = 0 ; j < 32 ; j++) {
		for (int i = 1 ; i <= N ; i++) {
			for (int k = 0 ; k < 2 ; k++) {
				if (j == 0) {
					dp[i][k][j] = nxt[i][k];
				} else {
					int x = dp[i][k][j-1];
					int u = abs(x);
					int v = x < 0;
					dp[i][k][j] = dp[u][v][j-1];
				}
			}
		}
	}

	for (int q = 0 ; q < Q ; q++) {
		int k = G[q];
		int ans = 0;
		for (int i = 1 ; i <= N ; i++) {
			int u = i, v = 0;
			for (int j = 31 ; j >= 0 ; j--) {
				if (k & (1 << j)) {
					int x = dp[u][v][j];
					u = abs(x);
					v = x < 0;
				}
			}
			// cerr << q << ": " << i << " " << u << endl;
			if (u == P + 1) {
				ans++;
			}
		}
		answer(ans);
	}
}

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