Submission #532496

#	Time	Username	Problem	Language	Result	Execution time	Memory
532496		pavement	Tropical Garden (IOI11_garden)	C++17	69 / 100	5025 ms	51216 KiB

garden

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

#define pb push_back
#define eb emplace_back
using ii = pair<int, int>;

int to[300005], anc[35][300005];
bool out[300005];
vector<int> bits, in_nodes;
vector<ii> _adj[300005];
map<int, int> chc;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	for (int i = 0; i < M; i++) {
		_adj[R[i][0]].eb(i, i << 1);
		_adj[R[i][1]].eb(i, i << 1 | 1);
	}
	for (int i = 0; i < N; i++) sort(_adj[i].begin(), _adj[i].end());
	for (int i = 0; i < M; i++) {
		if (_adj[R[i][1]].size() == 1) to[i << 1] = (i << 1) ^ 1;
		else to[i << 1] = ((_adj[R[i][1]][0].second >> 1) == i ? _adj[R[i][1]][1].second : _adj[R[i][1]][0].second);
		if (_adj[R[i][0]].size() == 1) to[i << 1 | 1] = (i << 1 | 1) ^ 1;
		else to[i << 1 | 1] = ((_adj[R[i][0]][0].second >> 1) == i ? _adj[R[i][0]][1].second : _adj[R[i][0]][0].second);
	}
	for (int i = 0; i < N; i++)
		if (!_adj[i].empty()) in_nodes.pb(_adj[i][0].second);
	for (int i = 0; i < M; i++) {
		if (R[i][0] == P) out[i << 1 | 1] = 1;
		if (R[i][1] == P) out[i << 1] = 1;
	}
	for (int k = 0; k < 30; k++) {
		for (int i = 0; i < (M << 1); i++)
			if (k == 0) anc[k][i] = to[i];
			else anc[k][i] = anc[k - 1][anc[k - 1][i]];
	}
	for (int i = 0, ans, curr, OG; i < Q; i++) {
		G[i]--;
		if (chc.find(G[i]) != chc.end()) {
			answer(chc[G[i]]);
			continue;
		}
		ans = 0;
		OG = G[i];
		bits.clear();
		for (int j = 0; G[i]; j++, G[i] >>= 1)
			if (G[i] & 1) bits.pb(j);
		for (int j : in_nodes) {
			curr = j;
			for (int k : bits)
				curr = anc[k][curr];
			if (out[curr]) ans++;
		}
		chc[OG] = ans;
		answer(ans);
	}
}

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