Submission #541286

#	Time	Username	Problem	Language	Result	Execution time	Memory
541286		sliviu	Werewolf (IOI18_werewolf)	C++17	100 / 100	687 ms	80840 KiB

werewolf

#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 (stderr)

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51