Submission #236869

#	Time	Username	Problem	Language	Result	Execution time	Memory
236869		srvlt	Tropical Garden (IOI11_garden)	C++14	100 / 100	3550 ms	111436 KiB

garden

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;

typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int max_N = 450007;
int n, m, p, cnt;
vi adj[max_N], g[max_N], gr[max_N];
pii edge[max_N], E[max_N];
map <pii, int> ind;

int zero[max_N], used[max_N], par[max_N], cyc[max_N], h[max_N];
vi bad, vec;

void dfs(int v) {
	used[v] = 1;
	for (int to : g[v]) {
		if (used[to] == 1) {
			int u = v, len = 1;
			vec.clear();
			while (u != to) {
				if (E[u].F == p) {
					vec.pb(u);
				}
				u = par[u];
				len++;
			}
			if (E[to].F == p) {
				vec.pb(to);
			}
			for (int i : vec) {
				cyc[i] = len;
			}
		}
		if (used[to] == 0) {
			par[to] = v;
			dfs(to);
		}
	}
	used[v] = 2;
}

void go(int v) {
	for (int to : gr[v]) {
		h[to] = h[v] + 1;
		go(to);
	}
}

int dist[2][max_N];
queue <int> q;

void bfs(int c, int s) {
	memset(& used, 0, sizeof(used));
	q.push(s);
	used[s] = 1;
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (int to : gr[v]) {
			if (!used[to]) {
				used[to] = 1;
				dist[c][to] = dist[c][v] + 1;
				q.push(to);
			}
		}
	}
}

int get_end(int v, int e) {
	return edge[e].F + edge[e].S - v;
}

int get(int k) {
	int res = 0;
	for (int i = 0; i < n; i++) {
		if (h[zero[i]] == k) {
			res++;
			continue;
		}
		for (int j = 0; j < (int)bad.size(); j++) {
			int c = cyc[bad[j]], d = dist[j][zero[i]];
			if (d == 0) {
				continue;
			}
			if (k >= d && (k - d) % c == 0) {
				res++;
				break;
			}
		}
	}
	return res;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n = N, m = M, p = P;
	for (int i = 0; i < m; i++) {
		adj[R[i][0]].pb(i + 1);
		adj[R[i][1]].pb(i + 1);
		edge[i + 1] = {R[i][0], R[i][1]};
	}
	for (int i = 0; i < n; i++) {
		E[cnt] = {i, 0};
		ind[{i, 0}] = cnt++;
		for (int j : adj[i]) {
			E[cnt] = {i, j};
			ind[{i, j}] = cnt++;
		}
	}
	for (int i = 0; i < n; i++) {
		int to = get_end(i, adj[i][0]);
		g[ind[{i, 0}]].pb(ind[{to, adj[i][0]}]);
		for (int j : adj[i]) {
			int tmp = (j == adj[i][0] && (int)adj[i].size() > 1);
			to = get_end(i, adj[i][tmp]);
			g[ind[{i, j}]].pb(ind[{to, adj[i][tmp]}]);
		}
	}
	for (int i = 0; i < cnt; i++) {
		for (int j : g[i]) {
			gr[j].pb(i);
		}
	}
	for (int i = 0; i < cnt; i++) {
		if (used[i] == 0) {
			par[i] = -1;
			dfs(i);
		}
	}
	for (int i : adj[p]) {
		int v = ind[{p, i}];
		if (cyc[v]) {
			bad.pb(v);
		}	else {
			go(v);
		}
	}
	for (int i = 0; i < (int)bad.size(); i++) {
		bfs(i, bad[i]);
	}
	for (int i = 0; i < cnt; i++) {
		if (E[i].S == 0) {
			zero[E[i].F] = i;
		}
	}
	for (int i = 0; i < Q; i++) {
		answer(get(G[i]));
	}
}

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