oj.uz

Submission #601845

# Submission time Handle Problem Language Result Execution time Memory
601845 2022-07-22T10:54:18 Z DanShaders Werewolf (IOI18_werewolf) C++17
100 / 100
 2522 ms 406820 KB 
//Cgrader.cpp
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;

const int N = 2e5 + 10;

const int MEMORY = 400 << 20;

char memory[MEMORY];
size_t memory_ptr = 0;

void *operator new(size_t sz) {
	auto res = memory + memory_ptr;
	memory_ptr += sz;
	return res;
}

void operator delete(void *) {}
void operator delete(void *, size_t) {}

struct Query {
	int s, e, l, r, i;
};

int color[N];
vector<int> g[N];

struct DSU {
	int parent[N];
	vector<int> comp[N];

	DSU() {
		iota(all(parent), 0);
		for (int i = 0; i < N; ++i) {
			comp[i].push_back(i);
		}
	}

	int get(int u) {
		if (u == parent[u]) {
			return u;
		}
		return parent[u] = get(parent[u]);
	}
} dsu;

struct DSU2 {
	int parent[N], rank[N];

	DSU2() {
		iota(all(parent), 0);
	}

	int get(int u) {
		if (u == parent[u]) {
			return u;
		}
		return parent[u] = get(parent[u]);
	}

	bool merge(int a, int b) {
		a = get(a);
		b = get(b);
		if (a == b) {
			return false;
		}
		if (rank[a] == rank[b]) {
			++rank[a];
		}
		if (rank[a] < rank[b]) {
			swap(a, b);
		}
		parent[b] = a;
		return true;
	}
} dsu2;

bool check_reachable(int u, int barrier, int c, int p = -1) {
	if (u < barrier) {
		return false;
	}
	if (color[u] == c) {
		return true;
	}
	for (int v : g[u]) {
		if (v != p && check_reachable(v, barrier, c, u)) {
			return true;
		}
	}
	return false;
}

char used[N];
int sz[N];

int dfs_sz(int u, int p = -1) {
	sz[u] = 1;
	for (int v : g[u]) {
		if (v != p && !used[v]) {
			sz[u] += dfs_sz(v, u);
		}
	}
	return sz[u];
}

int find_centroid(int u, int csz, int p = -1) {
	for (int v : g[u]) {
		if (v != p && !used[v] && 2 * sz[v] > csz) {
			return find_centroid(v, csz, u);
		}
	}
	return u;
}

const int LOG = 20;

int gmn[LOG][N];

struct Node {
	int depth;
	int parent;
	vector<int> children;
	int version;
	unordered_map<int, int> where;
};

int current_version = 15;

Node node_at[N];

int centroid_dfs(int u, int parent = -1, int depth = 0) {
	u = find_centroid(u, dfs_sz(u));

	auto &node = node_at[u];
	node.depth = depth;
	node.parent = parent;

	queue<tuple<int, int, int>> bfs;
	bfs.push({u, u, -1});
	while (sz(bfs)) {
		auto [v, mn, p] = bfs.front();
		gmn[depth][v] = node.where[v] = mn;
		bfs.pop();
		for (int w : g[v]) {
			if (p != w && !used[w]) {
				bfs.push({w, min(mn, w), v});
			}
		}
	}

	used[u] = 1;
	for (int v : g[u]) {
		if (!used[v]) {
			node.children.push_back(centroid_dfs(v, u, depth + 1));
		}
	}
	return u;
}

vector<int> check_validity(int, vector<int> us, vector<int> vs, vector<int> qs, vector<int> qe, vector<int> ql, vector<int> qr) {
	vector<Query> queries;
	for (int i = 0; i < sz(qs); ++i) {
		queries.push_back({qe[i], qs[i], qr[i], ql[i], i});
	}
	vector<pair<int, int>> e1, e2;
	for (int i = 0; i < sz(us); ++i) {
		e1.emplace_back(us[i], vs[i]);
	}
	e2 = e1;
	iota(all(color), 0);
	sort(all(e1), [](const auto &x, const auto &y) {
		return max(x.x, x.y) < max(y.x, y.y);
	});
	sort(all(e2), [](const auto &x, const auto &y) {
		return min(x.x, x.y) > min(y.x, y.y);
	});
	for (auto [u, v] : e2) {
		if (dsu2.merge(u, v)) {
			g[u].push_back(v);
			g[v].push_back(u);
		}
	}
	sort(all(queries), [](const auto &x, const auto &y) {
		return x.l < y.l;
	});
	vector<int> ans(sz(queries));

	centroid_dfs(0);

	int e1i = 0;
	for (auto [s, e, l, r, i] : queries) {
		while (e1i < sz(e1) && max(e1[e1i].x, e1[e1i].y) <= l) {
			int a = dsu.get(e1[e1i].x), b = dsu.get(e1[e1i].y);
			++e1i;
			if (a == b) {
				continue;
			}
			if (sz(dsu.comp[a]) < sz(dsu.comp[b])) {
				swap(a, b);
			}

			++current_version;
			for (int u : dsu.comp[b]) {
				auto curr = u;
				while (curr != -1 && node_at[curr].version != current_version) {
					node_at[curr].version = current_version;

					auto it = node_at[curr].where.find(a);
					if (it == node_at[curr].where.end()) {
						node_at[curr].where[a] = node_at[curr].where[b];
					} else {
						it->second = max(it->second, node_at[curr].where[b]);
					}
					curr = node_at[curr].parent;
				}
				color[u] = a;
			}
			dsu.comp[a].insert(end(dsu.comp[a]), all(dsu.comp[b]));
			vector<int>().swap(dsu.comp[b]);

			dsu.parent[b] = a;
		}
		auto curr = e;
		while (curr != -1) {
			if (gmn[node_at[curr].depth][e] >= r) {
				auto it = node_at[curr].where.find(color[s]);
				if (it != node_at[curr].where.end() && it->second >= r) {
					ans[i] = 1;
					break;
				}
			}
			curr = node_at[curr].parent;
		}
		// ans[i] = check_reachable(e, r, color[s]);
	}
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31764 KB Output is correct
2 Correct 19 ms 31700 KB Output is correct
3 Correct 21 ms 31700 KB Output is correct
4 Correct 19 ms 31632 KB Output is correct
5 Correct 20 ms 31668 KB Output is correct
6 Correct 23 ms 31652 KB Output is correct
7 Correct 23 ms 31692 KB Output is correct
8 Correct 18 ms 31760 KB Output is correct
9 Correct 17 ms 31740 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31764 KB Output is correct
2 Correct 19 ms 31700 KB Output is correct
3 Correct 21 ms 31700 KB Output is correct
4 Correct 19 ms 31632 KB Output is correct
5 Correct 20 ms 31668 KB Output is correct
6 Correct 23 ms 31652 KB Output is correct
7 Correct 23 ms 31692 KB Output is correct
8 Correct 18 ms 31760 KB Output is correct
9 Correct 17 ms 31740 KB Output is correct
10 Correct 26 ms 35356 KB Output is correct
11 Correct 25 ms 35296 KB Output is correct
12 Correct 28 ms 36068 KB Output is correct
13 Correct 28 ms 35300 KB Output is correct
14 Correct 33 ms 35112 KB Output is correct
15 Correct 34 ms 35728 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2522 ms 401740 KB Output is correct
2 Correct 887 ms 379668 KB Output is correct
3 Correct 965 ms 383792 KB Output is correct
4 Correct 1366 ms 390136 KB Output is correct
5 Correct 1470 ms 390600 KB Output is correct
6 Correct 1814 ms 393204 KB Output is correct
7 Correct 2326 ms 406820 KB Output is correct
8 Correct 783 ms 379800 KB Output is correct
9 Correct 813 ms 383640 KB Output is correct
10 Correct 1132 ms 390068 KB Output is correct
11 Correct 1222 ms 390624 KB Output is correct
12 Correct 1758 ms 395608 KB Output is correct
13 Correct 940 ms 372196 KB Output is correct
14 Correct 945 ms 372156 KB Output is correct
15 Correct 907 ms 372268 KB Output is correct
16 Correct 943 ms 372320 KB Output is correct
17 Correct 2270 ms 406236 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31764 KB Output is correct
2 Correct 19 ms 31700 KB Output is correct
3 Correct 21 ms 31700 KB Output is correct
4 Correct 19 ms 31632 KB Output is correct
5 Correct 20 ms 31668 KB Output is correct
6 Correct 23 ms 31652 KB Output is correct
7 Correct 23 ms 31692 KB Output is correct
8 Correct 18 ms 31760 KB Output is correct
9 Correct 17 ms 31740 KB Output is correct
10 Correct 26 ms 35356 KB Output is correct
11 Correct 25 ms 35296 KB Output is correct
12 Correct 28 ms 36068 KB Output is correct
13 Correct 28 ms 35300 KB Output is correct
14 Correct 33 ms 35112 KB Output is correct
15 Correct 34 ms 35728 KB Output is correct
16 Correct 2522 ms 401740 KB Output is correct
17 Correct 887 ms 379668 KB Output is correct
18 Correct 965 ms 383792 KB Output is correct
19 Correct 1366 ms 390136 KB Output is correct
20 Correct 1470 ms 390600 KB Output is correct
21 Correct 1814 ms 393204 KB Output is correct
22 Correct 2326 ms 406820 KB Output is correct
23 Correct 783 ms 379800 KB Output is correct
24 Correct 813 ms 383640 KB Output is correct
25 Correct 1132 ms 390068 KB Output is correct
26 Correct 1222 ms 390624 KB Output is correct
27 Correct 1758 ms 395608 KB Output is correct
28 Correct 940 ms 372196 KB Output is correct
29 Correct 945 ms 372156 KB Output is correct
30 Correct 907 ms 372268 KB Output is correct
31 Correct 943 ms 372320 KB Output is correct
32 Correct 2270 ms 406236 KB Output is correct
33 Correct 1348 ms 309644 KB Output is correct
34 Correct 295 ms 78948 KB Output is correct
35 Correct 1491 ms 328080 KB Output is correct
36 Correct 1755 ms 346040 KB Output is correct
37 Correct 1400 ms 323532 KB Output is correct
38 Correct 1772 ms 341864 KB Output is correct
39 Correct 1473 ms 318756 KB Output is correct
40 Correct 1757 ms 358004 KB Output is correct
41 Correct 1248 ms 313832 KB Output is correct
42 Correct 1722 ms 345516 KB Output is correct
43 Correct 1814 ms 353004 KB Output is correct
44 Correct 1357 ms 318164 KB Output is correct
45 Correct 1366 ms 321500 KB Output is correct
46 Correct 1124 ms 321924 KB Output is correct
47 Correct 952 ms 341096 KB Output is correct
48 Correct 967 ms 352408 KB Output is correct
49 Correct 953 ms 342060 KB Output is correct
50 Correct 924 ms 347748 KB Output is correct
51 Correct 1785 ms 351768 KB Output is correct
52 Correct 1673 ms 349892 KB Output is correct