oj.uz

Submission #533253

# Submission time Handle Problem Language Result Execution time Memory
533253 2022-03-05T08:04:42 Z pavement Tropical Garden (IOI11_garden) C++17
69 / 100
 575 ms 262148 KB 
#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[300005], cnt[300005], _cnt2[600005], dr[300005], link[300005], rt[300005], sz[300005], to[300005], *cnt2 = _cnt2 + 300000;
bool on_cyc[300005], out[300005];
vector<int> in_nodes, adj[300005];
vector<ii> _adj[300005], qu[300005];

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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21708 KB Output is correct
2 Correct 16 ms 21580 KB Output is correct
3 Correct 11 ms 21624 KB Output is correct
4 Correct 11 ms 21436 KB Output is correct
5 Correct 12 ms 21452 KB Output is correct
6 Correct 12 ms 21832 KB Output is correct
7 Correct 11 ms 21432 KB Output is correct
8 Correct 12 ms 21564 KB Output is correct
9 Correct 15 ms 22220 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21708 KB Output is correct
2 Correct 16 ms 21580 KB Output is correct
3 Correct 11 ms 21624 KB Output is correct
4 Correct 11 ms 21436 KB Output is correct
5 Correct 12 ms 21452 KB Output is correct
6 Correct 12 ms 21832 KB Output is correct
7 Correct 11 ms 21432 KB Output is correct
8 Correct 12 ms 21564 KB Output is correct
9 Correct 15 ms 22220 KB Output is correct
10 Correct 11 ms 21440 KB Output is correct
11 Correct 26 ms 25392 KB Output is correct
12 Correct 60 ms 29128 KB Output is correct
13 Correct 64 ms 39080 KB Output is correct
14 Correct 209 ms 43572 KB Output is correct
15 Correct 197 ms 44472 KB Output is correct
16 Correct 167 ms 40580 KB Output is correct
17 Correct 160 ms 39724 KB Output is correct
18 Correct 54 ms 28876 KB Output is correct
19 Correct 205 ms 43592 KB Output is correct
20 Correct 192 ms 44312 KB Output is correct
21 Correct 219 ms 40352 KB Output is correct
22 Correct 161 ms 39540 KB Output is correct
23 Correct 176 ms 45708 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21708 KB Output is correct
2 Correct 16 ms 21580 KB Output is correct
3 Correct 11 ms 21624 KB Output is correct
4 Correct 11 ms 21436 KB Output is correct
5 Correct 12 ms 21452 KB Output is correct
6 Correct 12 ms 21832 KB Output is correct
7 Correct 11 ms 21432 KB Output is correct
8 Correct 12 ms 21564 KB Output is correct
9 Correct 15 ms 22220 KB Output is correct
10 Correct 11 ms 21440 KB Output is correct
11 Correct 26 ms 25392 KB Output is correct
12 Correct 60 ms 29128 KB Output is correct
13 Correct 64 ms 39080 KB Output is correct
14 Correct 209 ms 43572 KB Output is correct
15 Correct 197 ms 44472 KB Output is correct
16 Correct 167 ms 40580 KB Output is correct
17 Correct 160 ms 39724 KB Output is correct
18 Correct 54 ms 28876 KB Output is correct
19 Correct 205 ms 43592 KB Output is correct
20 Correct 192 ms 44312 KB Output is correct
21 Correct 219 ms 40352 KB Output is correct
22 Correct 161 ms 39540 KB Output is correct
23 Correct 176 ms 45708 KB Output is correct
24 Correct 15 ms 23492 KB Output is correct
25 Runtime error 575 ms 262148 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -