oj.uz

Submission #541284

# Submission time Handle Problem Language Result Execution time Memory
541284 2022-03-22T22:25:07 Z sliviu Werewolf (IOI18_werewolf) C++17
34 / 100
 592 ms 70508 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(n + 1);
		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
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 Runtime error 1 ms 432 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
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 Runtime error 1 ms 432 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 60840 KB Output is correct
2 Correct 481 ms 67980 KB Output is correct
3 Correct 484 ms 63256 KB Output is correct
4 Correct 464 ms 61388 KB Output is correct
5 Correct 492 ms 61360 KB Output is correct
6 Correct 563 ms 61028 KB Output is correct
7 Correct 529 ms 60648 KB Output is correct
8 Correct 462 ms 67768 KB Output is correct
9 Correct 394 ms 63704 KB Output is correct
10 Correct 399 ms 60092 KB Output is correct
11 Correct 430 ms 59892 KB Output is correct
12 Correct 458 ms 61336 KB Output is correct
13 Correct 462 ms 70316 KB Output is correct
14 Correct 452 ms 70508 KB Output is correct
15 Correct 457 ms 70320 KB Output is correct
16 Correct 453 ms 70408 KB Output is correct
17 Correct 502 ms 60672 KB Output is correct

Subtask #4
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 Runtime error 1 ms 432 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -