oj.uz

Submission #541286

# Submission time Handle Problem Language Result Execution time Memory
541286 2022-03-22T22:39:19 Z sliviu Werewolf (IOI18_werewolf) C++17
100 / 100
 687 ms 80840 KB 
#include "werewolf.h"
#include <bits/stdc++.h>    
 
using namespace std;
 
vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int q = S.size(), cur = 0;
	vector<vector<int>> G(n);
	vector<int> id(n), ans(q), tin[2], tout[2], subtree[2], y(n + 1), bit(n + 1);
	iota(id.begin(), id.end(), 0);
	for (int i = 0; i < X.size(); ++i)
		G[X[i]].emplace_back(Y[i]), G[Y[i]].emplace_back(X[i]);
	for (const auto& [l, s] : {make_tuple(L,S),make_tuple(R,E)}) {
		tin[cur].resize(n + 1), tout[cur].resize(n + 1), subtree[cur].resize(q);
		reverse(id.begin(), id.end());
		vector<vector<int>> GT(n);
		vector<vector<pair<int, int>>> Q(n);
		for (int i = 0; i < q; ++i) 
			Q[l[i]].emplace_back(s[i], i);
		vector<int> seen(n), p(n);
		iota(p.begin(), p.end(), 0);
		function<int(int)> get = [&](int x) {
			if (p[x] == x)
				return x;
			return p[x] = get(p[x]);
		};
		int t = 0;
		for (auto i : id) {
			for (auto x : G[i])
				if (seen[x] && (x = get(x)) != i) {
					p[x] = i;
					GT[i].emplace_back(x), GT[x].emplace_back(i);
				}
			for (auto [pos, nr] : Q[i])
				subtree[cur][nr] = get(pos);
			seen[i] = 1;
		}
		function<void(int, int)> dfs = [&](int node, int last) {
			tin[cur][node] = ++t;
			for (auto x : GT[node])
				if (x != last)
					dfs(x, node);
			tout[cur][node] = t;
		};
		dfs(id.back(), -1);
		++cur;
	}
	for (int i = 0; i < n; ++i)
		y[tin[0][i]] = tin[1][i];
	auto update = [&](int pos) {
		for (int i = pos; i <= n; i += i & -i)
			++bit[i];
	};
	auto query = [&](int pos) {
		int ans = 0;
		for (int i = pos; i; i -= i & -i)
			ans += bit[i];
		return ans;
	};
	vector<vector<pair<int, int>>> Q(n+1);
	for (int i = 0; i < q; ++i)
		Q[tin[0][subtree[0][i]] - 1].emplace_back(i, -1),
		Q[tout[0][subtree[0][i]]].emplace_back(i, 1);
	for (int i = 1; i <= n; ++i) {
		update(y[i]);
		for (auto [nr, sgn] : Q[i])
			ans[nr] += sgn * (query(tout[1][subtree[1][nr]]) - query(tin[1][subtree[1][nr]] - 1));
	}
	for (int i = 0; i < q; ++i)
		ans[i] = !!ans[i];
	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:11:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for (int i = 0; i < X.size(); ++i)
      |                  ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 6 ms 1236 KB Output is correct
11 Correct 6 ms 1208 KB Output is correct
12 Correct 5 ms 1108 KB Output is correct
13 Correct 6 ms 1492 KB Output is correct
14 Correct 5 ms 1364 KB Output is correct
15 Correct 6 ms 1364 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 52612 KB Output is correct
2 Correct 527 ms 59400 KB Output is correct
3 Correct 529 ms 54852 KB Output is correct
4 Correct 477 ms 53076 KB Output is correct
5 Correct 544 ms 52880 KB Output is correct
6 Correct 572 ms 52740 KB Output is correct
7 Correct 516 ms 52396 KB Output is correct
8 Correct 465 ms 59612 KB Output is correct
9 Correct 406 ms 55372 KB Output is correct
10 Correct 443 ms 51576 KB Output is correct
11 Correct 434 ms 51532 KB Output is correct
12 Correct 460 ms 52992 KB Output is correct
13 Correct 488 ms 61960 KB Output is correct
14 Correct 473 ms 61960 KB Output is correct
15 Correct 471 ms 62068 KB Output is correct
16 Correct 480 ms 61960 KB Output is correct
17 Correct 523 ms 52144 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 6 ms 1236 KB Output is correct
11 Correct 6 ms 1208 KB Output is correct
12 Correct 5 ms 1108 KB Output is correct
13 Correct 6 ms 1492 KB Output is correct
14 Correct 5 ms 1364 KB Output is correct
15 Correct 6 ms 1364 KB Output is correct
16 Correct 608 ms 52612 KB Output is correct
17 Correct 527 ms 59400 KB Output is correct
18 Correct 529 ms 54852 KB Output is correct
19 Correct 477 ms 53076 KB Output is correct
20 Correct 544 ms 52880 KB Output is correct
21 Correct 572 ms 52740 KB Output is correct
22 Correct 516 ms 52396 KB Output is correct
23 Correct 465 ms 59612 KB Output is correct
24 Correct 406 ms 55372 KB Output is correct
25 Correct 443 ms 51576 KB Output is correct
26 Correct 434 ms 51532 KB Output is correct
27 Correct 460 ms 52992 KB Output is correct
28 Correct 488 ms 61960 KB Output is correct
29 Correct 473 ms 61960 KB Output is correct
30 Correct 471 ms 62068 KB Output is correct
31 Correct 480 ms 61960 KB Output is correct
32 Correct 523 ms 52144 KB Output is correct
33 Correct 603 ms 63016 KB Output is correct
34 Correct 253 ms 38428 KB Output is correct
35 Correct 587 ms 67292 KB Output is correct
36 Correct 565 ms 62224 KB Output is correct
37 Correct 600 ms 66040 KB Output is correct
38 Correct 648 ms 63104 KB Output is correct
39 Correct 587 ms 79960 KB Output is correct
40 Correct 687 ms 72736 KB Output is correct
41 Correct 555 ms 65272 KB Output is correct
42 Correct 520 ms 62708 KB Output is correct
43 Correct 645 ms 72812 KB Output is correct
44 Correct 575 ms 66048 KB Output is correct
45 Correct 505 ms 80840 KB Output is correct
46 Correct 469 ms 80504 KB Output is correct
47 Correct 479 ms 70532 KB Output is correct
48 Correct 469 ms 70336 KB Output is correct
49 Correct 479 ms 70552 KB Output is correct
50 Correct 475 ms 70388 KB Output is correct
51 Correct 579 ms 71376 KB Output is correct
52 Correct 601 ms 71392 KB Output is correct