Submission #533255

#	Time	Username	Problem	Language	Result	Execution time	Memory
533255		pavement	Tropical Garden (IOI11_garden)	C++17	69 / 100	523 ms	262148 KiB

garden

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

int cur_rt, ans[600050], cnt[600050], _cnt2[600050], dr[600050], link[300005], rt[600050], sz[600050], to[600050], *cnt2 = _cnt2 + 300005;
bool on_cyc[600050], out[600050];
vector<int> in_nodes, adj[600050];
vector<ii> _adj[600050], qu[600050];

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	link[b] = a;
}

void dfs(int n, int e = -1, int d = 0) {
	rt[n] = cur_rt;
	dr[n] = d;
	for (auto u : adj[n]) if (u != e && !on_cyc[u]) dfs(u, n, d + 1);
}

void dfs2(int n, int e = -1, int d = 0) {
	if (out[n]) cnt[d]++;
	if (!on_cyc[n])
		for (auto [j, idx] : qu[n])
			ans[idx] += cnt[d - j];
	for (auto u : adj[n]) if (u != e && !on_cyc[u]) dfs2(u, n, d + 1);
	if (out[n]) cnt[d]--;
}

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);
	}
	iota(link, link + 2 * M, 0);
	fill(sz, sz + 2 * M, 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 i = 0; i < 2 * M; i++) {
		unite(i, to[i]);
		adj[to[i]].pb(i);
	}
	for (int i = 0; i < 2 * M; i++) {
		if (i == find(i)) {
			int tort = i, hare = i;
			do {
				tort = to[tort];
				hare = to[to[hare]];
			} while (tort != hare);
			do {
				on_cyc[tort] = 1;
				tort = to[tort];
			} while (tort != hare);
			do {
				cur_rt = tort;
				dfs(tort);
				tort = to[tort];
			} while (tort != hare);
		}
	}
	for (int i = 0, ans, curr, OG; i < Q; i++) {
		G[i]--;
		for (int j : in_nodes) {
			if (G[i] >= dr[j]) qu[rt[j]].eb(G[i] - dr[j], i);
			else qu[j].eb(G[i], i);
		}
	}
	for (int i = 0; i < 2 * M; i++)
		if (on_cyc[i]) dfs2(i);
	for (int i = 0; i < 2 * M; i++) {
		if (i == find(i)) {
			vector<int> upd;
			int tort = i, hare = i;
			do {
				tort = to[tort];
				hare = to[to[hare]];
			} while (tort != hare);
			int cyc = 0, off = 0, steps = 0;
			do {
				cyc++;
				upd.pb(steps);
				if (out[tort]) cnt2[steps]++;
				tort = to[tort];
				steps++;
			} while (tort != hare);
			do {
				for (auto [j, idx] : qu[tort])
					ans[idx] += cnt2[j % cyc - off];
				if (out[tort]) {
					upd.pb(-off);
					upd.pb(cyc - off);
					cnt2[-off]--;
					cnt2[cyc - off]++;
				}
				off--;
				tort = to[tort];
			} while (tort != hare);
			for (int j : upd) cnt2[j] = 0;
		}
	}
	for (int i = 0; i < Q; i++) answer(ans[i]);
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:89:18: warning: unused variable 'ans' [-Wunused-variable]
   89 |  for (int i = 0, ans, curr, OG; i < Q; i++) {
      |                  ^~~
garden.cpp:89:23: warning: unused variable 'curr' [-Wunused-variable]
   89 |  for (int i = 0, ans, curr, OG; i < Q; i++) {
      |                       ^~~~
garden.cpp:89:29: warning: unused variable 'OG' [-Wunused-variable]
   89 |  for (int i = 0, ans, curr, OG; i < Q; i++) {
      |                             ^~

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