Submission #765171

#	Time	Username	Problem	Language	Result	Execution time	Memory
765171		ono_de206	Werewolf (IOI18_werewolf)	C++14	100 / 100	466 ms	89412 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 2e5 + 10;
int p[mxn], in[2][mxn], out[2][mxn], T;

int find(int x) {
	return p[x] == x ? x : p[x] = find(p[x]);
}

vector<vector<int>> adj[2], g;
vector<int> order[2];

void unite(int x, int y, int id) {
	x = find(x);
	y = find(y);
	if(x == y) return;
	p[y] = x;
	adj[id][x].pb(y);
}

void dfs(int to, int id) {
	in[id][to] = T++;
	order[id].pb(to);
	for(int x : adj[id][to]) {
		dfs(x, id);
	}
	out[id][to] = T - 1;
}

int d[mxn * 4];

void update(int l, int r, int i, int id, int x) {
	if(l == r) {
		d[i] = x;
		return;
	}
	int m = (l + r) / 2;
	if(id <= m) update(l, m, i * 2, id, x);
	else update(m + 1, r, i * 2 + 1, id, x);
	d[i] = min(d[i * 2], d[i * 2 + 1]);
}

int query(int l, int r, int i, int x, int y) {
	if(l >= x && r <= y) return d[i];
	int m = (l + r) / 2;
	if(y <= m) return query(l, m, i * 2, x, y);
	if(x > m) return query(m + 1, r, i * 2 + 1, x, y);
	return min(query(l, m, i * 2, x, y), query(m + 1, r, i * 2 + 1, x, y));
}

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 = E.size();
	vector<int> ret(Q);

	g = adj[0] = adj[1] = vector<vector<int>>(n);

	for(int i = 0; i < X.size(); i++) {
		g[X[i]].pb(Y[i]);
		g[Y[i]].pb(X[i]);
	}

	vector<int> pa(Q), pb(Q);
	vector<vector<int>> v;

	auto setDsu = [&]() -> void {
		v.clear();
		v.resize(n);
		for(int i = 0; i < n; i++) {
			p[i] = i;
		}
	};

	setDsu();
	{
		for(int i = 0; i < Q; i++) {
			v[L[i]].pb(i);
		}

		for(int i = n - 1; i >= 0; i--) {
			for(int x : g[i]) {
				if(x > i) {
					unite(i, x, 0);
				}
			}
			for(int id : v[i]) {
				pa[id] = find(S[id]);
			}
		}
	}

	setDsu();
	{
		for(int i = 0; i < Q; i++) {
			v[R[i]].pb(i);
		}

		for(int i = 0; i < n; i++) {
			for(int x : g[i]) {
				if(x < i) {
					unite(i, x, 1);
				}
			}
			for(int id : v[i]) {
				pb[id] = find(E[id]);
			}
		}
	}

	dfs(0, 0); T = 0;
	dfs(n - 1, 1); T = 0;

	vector<vector<pair<pair<int, int>, pair<int, int>>>> qu(n);
	for(int i = 0; i < Q; i++) {
		int l1 = in[0][pa[i]], r1 = out[0][pa[i]];
		int l2 = in[1][pb[i]], r2 = out[1][pb[i]];
		qu[l1].pb({{i, r1}, {l2, r2}});
	}

	for(int i = 0; i < n; i++) {
		update(0, n - 1, 1, in[1][order[0][i]], i);
	}

	for(int i = 0; i < n; i++) {
		for(auto it : qu[i]) {
			int r = it.ff.ss, L = it.ss.ff, R = it.ss.ss, id = it.ff.ff;
			int mn = query(0, n - 1, 1, L, R);
			if(mn <= r) ret[id] = 1;
			else ret[id] = 0;
		}
		update(0, n - 1, 1, in[1][order[0][i]], n + 10);
	}
	return ret;
}

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:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0; i < X.size(); i++) {
      |                 ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51