Submission #1087527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087527		vincentbucourt1	Tropical Garden (IOI11_garden)	C++14	0 / 100	6 ms	14680 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second

const int INF = 1e9;
const int MAXN = 2 * 150001;

int V, E, dest;
vector<int> graph[MAXN];
int lenMove[MAXN];

int adj[MAXN];
vector<int> revAdj[MAXN];

int jump[MAXN][32];

int distGo (int node, int len) {
	for (int i = 0; i < 32; i++) {
		if (len & (1 << i)) {
			node = jump[node][i];
		}
	}
	return node;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {

	V = N, E = M, dest = P;
	for (int i = 0; i < Q; i++) {
		lenMove[i] = G[i];
	}

	for (int i = 0; i < E; i++) {
		graph[R[i][0]].push_back(R[i][1]);
		graph[R[i][1]].push_back(R[i][0]);
	}

	for (int i = 0; i < V; i++) {
		if (graph[i].size() > 1 && graph[graph[i][0]][0] == i) {
			adj[i] = graph[i][0] + V;
			revAdj[adj[i]].push_back(i);
		}
		else {
			adj[i] = graph[i][0];
			revAdj[adj[i]].push_back(i);
		}
	}

	for (int i = 0; i < V; i++) {
		if (graph[i].size() > 1 && graph[graph[i][1]][0] == i) {
			adj[i + V] = graph[i][1] + V;
			revAdj[adj[i + V]].push_back(i + V);
		}
		else if (graph[i].size() == 1 && graph[graph[i][0]][0] == i) {
			adj[i + V] = graph[i][0] + V;
			revAdj[adj[i + V]].push_back(i + V);
		}
		else {
			adj[i + V] = graph[i][0];
			revAdj[adj[i + V]].push_back(i + V);
		}
	}

	for (int i = 0; i < 2*V; i++) {
		jump[i][0] = adj[i];
	}

	for (int node = 0; node < 2*V; node++) {
		for (int i = 1; i < 32; i++) {
			jump[node][i] = jump[jump[node][i-1]][i-1];
		}
	}

	cout << adj[8] << "\n";

	int endOn;
	int ans;
	for (int q = 0; q < Q; q++) {
		ans = 0;
		for (int node = 0; node < V; node++) {
			endOn = distGo(node, lenMove[q]);
			if (endOn == dest || endOn == dest+V) {
				ans++;
			}
		}
		answer(ans);
	}
}

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