oj.uz

Submission #465586

# Submission time Handle Problem Language Result Execution time Memory
465586 2021-08-16T12:32:16 Z prvocislo Werewolf (IOI18_werewolf) C++17
100 / 100
 905 ms 126236 KB 
#include "werewolf.h"
#include <vector>
#include <set>
using namespace std;

const int maxn = 2e5 + 5;
int pa[maxn], siz[maxn], query_size[maxn], tin[maxn], query_l[maxn], query_r[maxn], time = 0;
vector<int> g[maxn], dsu_g[maxn], e1[maxn], e2[maxn];
set<int> node[maxn];
int root(int u) { return u == pa[u] ? u : root(pa[u]); }
void merge(int u, int v, bool type)
{
	u = root(u), v = root(v);
	if (u == v) return;
	if (siz[u] < siz[v]) swap(u, v); 
	pa[v] = u, siz[u] += siz[v];
	if (!type) dsu_g[u].push_back(v);
	else for (int i : node[v]) node[u].insert(i);
}
void dfs(int u)
{
	tin[u] = time++;
	for (int v : dsu_g[u]) dfs(v);
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) 
{
	for (int i = 0; i < x.size(); i++) g[x[i]].push_back(y[i]), g[y[i]].push_back(x[i]);
	int q = s.size();
	vector<int> ans(q, 0);
	for (int i = 0; i < q; i++) e1[l[i]].push_back(i), e2[r[i]].push_back(i);
	for (int i = 0; i < n; i++) pa[i] = i, siz[i] = 1;
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j : g[i]) if (j > i) merge(i, j, false);
		for (int j : e1[i])
		{
			query_l[j] = root(s[j]);
			query_size[j] = siz[query_l[j]];
		}
	}
	for (int i = 0; i < n; i++) if (pa[i] == i) dfs(i);
	for (int i = 0; i < q; i++) query_l[i] = tin[query_l[i]], query_r[i] = query_l[i] + query_size[i] - 1;
	for (int i = 0; i < n; i++) pa[i] = i, siz[i] = 1, node[i].insert(tin[i]);
	for (int i = 0; i < n; i++)
	{
		for (int j : g[i]) if (j < i) merge(i, j, true);
		for (int j : e2[i])
		{
			int u = root(e[j]);
			auto it = node[u].lower_bound(query_l[j]);
			if (it != node[u].end() && *it <= query_r[j]) ans[j] = true;
		}
	}
	return ans;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0; i < x.size(); i++) g[x[i]].push_back(y[i]), g[y[i]].push_back(x[i]);
      |                  ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28424 KB Output is correct
2 Correct 16 ms 28492 KB Output is correct
3 Correct 15 ms 28476 KB Output is correct
4 Correct 20 ms 28476 KB Output is correct
5 Correct 16 ms 28492 KB Output is correct
6 Correct 17 ms 28492 KB Output is correct
7 Correct 21 ms 28516 KB Output is correct
8 Correct 19 ms 28468 KB Output is correct
9 Correct 17 ms 28492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28424 KB Output is correct
2 Correct 16 ms 28492 KB Output is correct
3 Correct 15 ms 28476 KB Output is correct
4 Correct 20 ms 28476 KB Output is correct
5 Correct 16 ms 28492 KB Output is correct
6 Correct 17 ms 28492 KB Output is correct
7 Correct 21 ms 28516 KB Output is correct
8 Correct 19 ms 28468 KB Output is correct
9 Correct 17 ms 28492 KB Output is correct
10 Correct 22 ms 29384 KB Output is correct
11 Correct 23 ms 29480 KB Output is correct
12 Correct 24 ms 29644 KB Output is correct
13 Correct 22 ms 29280 KB Output is correct
14 Correct 27 ms 29276 KB Output is correct
15 Correct 31 ms 29428 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 126236 KB Output is correct
2 Correct 563 ms 83584 KB Output is correct
3 Correct 577 ms 89232 KB Output is correct
4 Correct 620 ms 97588 KB Output is correct
5 Correct 788 ms 98956 KB Output is correct
6 Correct 798 ms 105284 KB Output is correct
7 Correct 905 ms 125620 KB Output is correct
8 Correct 512 ms 83624 KB Output is correct
9 Correct 543 ms 88068 KB Output is correct
10 Correct 622 ms 96148 KB Output is correct
11 Correct 630 ms 97684 KB Output is correct
12 Correct 723 ms 105872 KB Output is correct
13 Correct 544 ms 82100 KB Output is correct
14 Correct 578 ms 82076 KB Output is correct
15 Correct 534 ms 82252 KB Output is correct
16 Correct 570 ms 82068 KB Output is correct
17 Correct 830 ms 124964 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28424 KB Output is correct
2 Correct 16 ms 28492 KB Output is correct
3 Correct 15 ms 28476 KB Output is correct
4 Correct 20 ms 28476 KB Output is correct
5 Correct 16 ms 28492 KB Output is correct
6 Correct 17 ms 28492 KB Output is correct
7 Correct 21 ms 28516 KB Output is correct
8 Correct 19 ms 28468 KB Output is correct
9 Correct 17 ms 28492 KB Output is correct
10 Correct 22 ms 29384 KB Output is correct
11 Correct 23 ms 29480 KB Output is correct
12 Correct 24 ms 29644 KB Output is correct
13 Correct 22 ms 29280 KB Output is correct
14 Correct 27 ms 29276 KB Output is correct
15 Correct 31 ms 29428 KB Output is correct
16 Correct 876 ms 126236 KB Output is correct
17 Correct 563 ms 83584 KB Output is correct
18 Correct 577 ms 89232 KB Output is correct
19 Correct 620 ms 97588 KB Output is correct
20 Correct 788 ms 98956 KB Output is correct
21 Correct 798 ms 105284 KB Output is correct
22 Correct 905 ms 125620 KB Output is correct
23 Correct 512 ms 83624 KB Output is correct
24 Correct 543 ms 88068 KB Output is correct
25 Correct 622 ms 96148 KB Output is correct
26 Correct 630 ms 97684 KB Output is correct
27 Correct 723 ms 105872 KB Output is correct
28 Correct 544 ms 82100 KB Output is correct
29 Correct 578 ms 82076 KB Output is correct
30 Correct 534 ms 82252 KB Output is correct
31 Correct 570 ms 82068 KB Output is correct
32 Correct 830 ms 124964 KB Output is correct
33 Correct 768 ms 95480 KB Output is correct
34 Correct 321 ms 54340 KB Output is correct
35 Correct 742 ms 86908 KB Output is correct
36 Correct 797 ms 98488 KB Output is correct
37 Correct 776 ms 87644 KB Output is correct
38 Correct 833 ms 94924 KB Output is correct
39 Correct 682 ms 79164 KB Output is correct
40 Correct 834 ms 90108 KB Output is correct
41 Correct 680 ms 88848 KB Output is correct
42 Correct 676 ms 96776 KB Output is correct
43 Correct 733 ms 86568 KB Output is correct
44 Correct 757 ms 88168 KB Output is correct
45 Correct 623 ms 78036 KB Output is correct
46 Correct 644 ms 77984 KB Output is correct
47 Correct 604 ms 82216 KB Output is correct
48 Correct 564 ms 82244 KB Output is correct
49 Correct 576 ms 82228 KB Output is correct
50 Correct 526 ms 82196 KB Output is correct
51 Correct 740 ms 88084 KB Output is correct
52 Correct 747 ms 88128 KB Output is correct