Submission #1087766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087766		Tob	Werewolf (IOI18_werewolf)	C++14	100 / 100	439 ms	109896 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;
typedef vector <int> vi;

const int N = 2e5 + 7;

struct T {
	int n, tim;
	vector <vector <int> > adj;
	vector <int> par, st, en, wh;
	vector <int> pa[20];
	void init(int n_) {
		n = n_; tim = 0;
		par.clear();
		st.resize(n); en.resize(n); adj.resize(n); wh.resize(n);
		for (int i = 0; i < n; i++) par.pb(i);
		for (int i = 0; i < 20; i++) pa[i].resize(n);
	}
	int find(int x) {return (par[x] == x) ? x : (par[x] = find(par[x]));}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return;
		par[y] = x;
		adj[x].pb(y);
	}
	void dfs(int x, int p = -1) {
		pa[0][x] = p;
		wh[tim] = x;
		st[x] = tim++;
		for (int y : adj[x]) dfs(y, x);
		en[x] = tim-1;
	}
	void fin() {
		for (int i = 1; i < 20; i++) {
			for (int j = 0; j < n; j++) {
				if (pa[i-1][j] != -1) pa[i][j] = pa[i-1][pa[i-1][j]];
				else pa[i][j] = -1;
			}
		}
	}
} tl, tr;

struct qu {
	int l, r, ix, o;
};
vector <qu> qe[N];

int fen[N];
void add(int x, int y) {for (x++; x < N; x += x & -x) fen[x] += y;}
int get(int x) {int out = 0; for (x++; x; x -= x & -x) out += fen[x]; return out;}

vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
	int m = X.size(), q = S.size();
	tl.init(n); tr.init(n);
	vector <vector <int> > adj(n);
	for (int i = 0; i < m; i++) {
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	for (int i = n-1; i >= 0; i--) for (auto x : adj[i]) if (x > i) tl.unite(i, x);
	for (int i = 0; i < n; i++) for (auto x : adj[i]) if (x < i) tr.unite(i, x);
	tl.dfs(0);
	tl.fin();
	tr.dfs(n-1);
	tr.fin();
	for (int i = 0; i < q; i++) {
		int x = S[i];
		for (int j = 19; j >= 0; j--) if (tl.pa[j][x] != -1 && tl.pa[j][x] >= L[i]) x = tl.pa[j][x];
		int a = tl.st[x], b = tl.en[x];
		x = E[i];
		for (int j = 19; j >= 0; j--) if (tr.pa[j][x] != -1 && tr.pa[j][x] <= R[i]) x = tr.pa[j][x];
		int c = tr.st[x], d = tr.en[x];
		if (a) qe[a-1].pb({c, d, i, -1});
		qe[b].pb({c, d, i, 1});
	}
	vector <int> a(n), res(q, 0);
	for (int i = 0; i < n; i++) a[i] = tr.st[tl.wh[i]];
	for (int i = 0; i < n; i++) {
		add(a[i], 1);
		for (auto x : qe[i]) res[x.ix] += (get(x.r)-get(x.l-1))*x.o;
	}
	for (int i = 0; i < q; i++) if (res[i]) res[i] = 1;
	return res;
}

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