Submission #296947

#	Time	Username	Problem	Language	Result	Execution time	Memory
296947		ChrisT	Werewolf (IOI18_werewolf)	C++17	100 / 100	1258 ms	120188 KiB

werewolf

#include <bits/stdc++.h> 
#include "werewolf.h"
using namespace std;
const int MN = 2e5 + 3;
struct Query {
	int l,r,l2,r2,id;
};
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 m = (int)x.size(), qq = (int)s.size(), LOG = __lg(n) + 1;
	vector<vector<int>> aaa(n+1); array<vector<vector<int>>,2> adj;
	for (int j = 0; j < 2; j++) adj[j].resize(n+1);
	vector<int> ret(qq);
	for (int i = 0; i < m; i++) {
		aaa[++x[i]].push_back(++y[i]);
		aaa[y[i]].push_back(x[i]);
	}
	vector<int> p(n+1);
	iota(p.begin(),p.end(),0); //1 is for >=, 0 is for <=
	const auto find = [&] (int x, const auto &find_ref) -> int {
		return p[x] == x ? x : p[x] = find_ref(p[x],find_ref);
	};
	const auto merge = [&] (int a, int b, bool lt) {
		if ((a = find(a,find)) == (b = find(b,find))) return;
		if ((a > b) ^ lt) swap(a,b);
		p[a] = b; adj[lt][b].push_back(a);
	};
	for (int i = n; i >= 1; i--) for (int j : aaa[i]) if (j > i) merge(i,j,1);
	iota(p.begin(),p.end(),0);
	for (int i = 1; i <= n; i++) for (int j : aaa[i]) if (j < i) merge(i,j,0);
	int tt = 0; array<vector<int>,2> st,ed,which; array<vector<vector<int>>,2> jmp, par;
	for (int i = 0; i < 2; i++) st[i].resize(n+1), ed[i].resize(n+1), which[i].resize(n+1), jmp[i].resize(n+1,vector<int>(LOG));
	const auto dfs = [&] (int cur, int p, int id, const auto &dfs_ref) -> void {
		 which[id][st[id][cur] = ++tt] = cur;
		 for (int i : adj[id][cur]) if (i != p) {
			 jmp[id][i][0] = cur;
			 for (int j = 1; j < LOG; j++)
				jmp[id][i][j] = jmp[id][jmp[id][i][j-1]][j-1];
			dfs_ref(i,cur,id,dfs_ref);
		 }
		 ed[id][cur] = tt;
	};
	dfs(1,-1,1,dfs);
	tt = 0;
	dfs(n,-1,0,dfs);
	const auto lift = [&] (int cur, int id, int x) { 
		for (int j = LOG - 1; ~j; j--)
			if (jmp[id][cur][j] && (jmp[id][cur][j] == x || (id ^ (jmp[id][cur][j] < x))))
				cur = jmp[id][cur][j];
		return cur;
	};
	vector<Query> queries(qq);
	for (int i = 0; i < qq; i++) {
		int golt = lift(++e[i],0,++r[i]), gogt = lift(++s[i],1,++l[i]);
		queries[i] = {st[0][golt],ed[0][golt],st[1][gogt],ed[1][gogt],i};
	}
	vector<int> tree(n*2);
	auto update = [&tree,&n] (int i, int v) {
		for (tree[i += n - 1] = v; i > 1; i >>= 1) 
			tree[i>>1] = max(tree[i],tree[i^1]);
	};
	auto query = [&tree,&n] (int l, int r) {
		int ret = 0;
		for (l += n-1, r += n; l < r; l >>= 1, r >>= 1) {
			if (l&1) ret = max(ret,tree[l++]);
			if (r&1) ret = max(ret,tree[--r]);
		}
		return ret;
	};
	sort(queries.begin(),queries.end(),[&](const Query &a, const Query &b){return a.r < b.r;});
	int pp = 1;
	for (Query &q : queries) {
		while (pp <= q.r) {
			update(st[1][which[0][pp]],pp);
			++pp;
		}
		ret[q.id] = query(q.l2,q.r2) >= q.l;
	}
	return ret;
}

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