Submission #144006

#	Time	Username	Problem	Language	Result	Execution time	Memory
144006		Minnakhmetov	Werewolf (IOI18_werewolf)	C++14	100 / 100	987 ms	135180 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 4e5 + 5, L = 20;
int w[N], tin[2][N], tout[2][N], p[2][N][L], t[N];
vector<int> g[N], tr[2][N];
int timer;

struct E {
	int t, x, y, i, k;
};

void upd(int x, int y) {
	for (; x < N; x |= x + 1)
		t[x] += y;
}

int que(int x) {
	int s = 0;
	for (; x >= 0; x = (x & (x + 1)) - 1)
		s += t[x];
	return s;
}

int findSet(int v) {
	return w[v] < 0 ? v : w[v] = findSet(w[v]);
}

void connect(int a, int b, int type) {
	a = findSet(a);
	b = findSet(b);

	if (a != b) {
		w[a] += w[b];
    	w[b] = a;
    	tr[type][a].push_back(b);
	}
}

void dfs(int node, int p[N][L], int tin[N], int tout[N], vector<int> tr[N]) {
	tin[node] = ++timer;
	for (int i = 1; i < L; i++) {
		p[node][i] = p[p[node][i - 1]][i - 1];
	}
	for (int to : tr[node]) {
		p[to][0] = node;
		dfs(to, p, tin, tout, tr);
	}
	tout[node] = timer;
}

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(), m = x.size();
	vector<int> ans(q);

	for (int i = 0; i < m; i++) {
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}

	fill(w, w + n, -1);

	for (int i = n - 1; i >= 0; i--) {
		for (int to : g[i]) {
			if (to > i) {
				connect(i, to, 0);
			}
		}
	}

	fill(w, w + n, -1);

	for (int i = 0; i < n; i++) {
		for (int to : g[i]) {
			if (to < i) {
				connect(i, to, 1);
			}
		}
	}

	timer = -1;
	dfs(0, p[0], tin[0], tout[0], tr[0]);

	timer = -1;
	fill(p[1][n - 1], p[1][n - 1] + L, n - 1);
	dfs(n - 1, p[1], tin[1], tout[1], tr[1]);

	vector<E> ev;

	for (int i = 0; i < q; i++) {
		int v1 = s[i], v2 = e[i];

		for (int j = L - 1; j >= 0; j--) {
			if (p[0][v1][j] >= l[i]) {
				v1 = p[0][v1][j];
			}
		}

		for (int j = L - 1; j >= 0; j--) {
			if (p[1][v2][j] <= r[i]) {
				v2 = p[1][v2][j];
			}
		}

		ev.push_back({ tout[0][v1], tin[1][v2], tout[1][v2], i, 1 });
		ev.push_back({ tin[0][v1] - 1, tin[1][v2], tout[1][v2], i, -1 });
	}

	for (int i = 0; i < n; i++) {
		ev.push_back({ tin[0][i], tin[1][i], -1, -1 });
	}

	sort(all(ev), [](E a, E b) {
		return a.t == b.t ? a.i == -1 : a.t < b.t;
	});

	for (E e : ev) {
		if (e.i == -1) {
			upd(e.x, 1);
		}
		else {
			ans[e.i] += (que(e.y) - que(e.x - 1)) * e.k;
		}
	}

	for (int i = 0; i < q; i++)
		ans[i] = ans[i] > 0;

  	return ans;
}

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