Submission #1088074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088074		vincentbucourt1	Tropical Garden (IOI11_garden)	C++14	49 / 100	78 ms	69336 KiB

garden

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

const ll INF = 1e9;
const ll MAXN = 2 * 150001;
 
ll V, E, dest;
vector<ll> graph[MAXN];
ll lenMove[MAXN];

ll adj[MAXN];
vector<ll> revAdj[MAXN];
 
ll jump[MAXN][33];
 
ll distGo (ll node, ll len) {
	for (ll i = 0; i < 33; i++) {
		if (len & (1ll << 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 (ll i = 0; i < Q; i++) {
		lenMove[i] = G[i];
	}
 
	for (ll i = 0; i < E; i++) {
		graph[R[i][0]].push_back(R[i][1]);
		graph[R[i][1]].push_back(R[i][0]);
	}
 
	for (ll i = 0; i < V; i++) {
		if (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 (ll 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][1];
			revAdj[adj[i + V]].push_back(i + V);
		}
	}
 
	for (ll i = 0; i < 2*V; i++) {
		jump[i][0] = adj[i];
	}
 
	for (ll i = 1; i < 33; i++) {
		for (ll node = 0; node < 2*N; node++) {
			jump[node][i] = jump[jump[node][i-1]][i-1];
		}
	}
 
	ll endOn;
	ll ans;
	for (ll q = 0; q < Q; q++) {
		ans = 0;
		for (ll node = 0; node < V; node++) {
			endOn = distGo(node, lenMove[q]);
			if (endOn == dest || endOn == dest+V) {
				ans++;
			}
		}
		answer(ans);
	}
}

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