Submission #114117

#	Time	Username	Problem	Language	Result	Execution time	Memory
114117		arman_ferdous	Werewolf (IOI18_werewolf)	C++17	100 / 100	948 ms	122060 KiB

werewolf

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

using vi = vector<int>;
const int N = 2e5+10;

int n, m, q;
int st[2][N], ft[2][N], p[2][18][N], posIn1[N];
vi UU[N], DD[N], t[2][N], eul[2];

int dsu[N];
void init() {
	for(int i = 0; i < n; i++)
		dsu[i] = i;
}
int find(int x) {
	if(dsu[x] == x) return x;
	return dsu[x] = find(dsu[x]);
}

void dfs(int u, int id) {
	st[id][u] = eul[id].size();
	eul[id].push_back(u);
	for(int v : t[id][u]) 
		dfs(v, id);
	ft[id][u] = eul[id].size()-1;
}

struct EpicDataStructureToSolveThisProblem{
	struct event{
		int x, y1, y2, type, QID;
		// type 0 = [, type 1 = point, type 2 = ]
		bool operator<(event o) const {
			if(x != o.x) return x < o.x;
			return type < o.type;
		}
	};
	vector<event> e;

	int ans[N], bit[N];
	void upd(int pos, int x) { while(pos < N) bit[pos] += x, pos += pos&-pos; }
	int get(int pos, int ret = 0) { while(pos > 0) ret += bit[pos], pos -= pos&-pos; return ret; }
	int rng(int l, int r) { return get(r) - get(l-1); }

	void add_point(int x, int y) { x++, y++; e.push_back({x, y, -1, 1, -1}); }
	void add_query(int x1, int x2, int y1, int y2, int id) {
		x1++, y1++, x2++, y2++;
		e.push_back({x1, y1, y2, 0, id});
		e.push_back({x2, y1, y2, 2, id});
	}

	void LineSweep() {
		sort(e.begin(),e.end());
		for(auto it : e) {
			if(it.type == 0) ans[it.QID] = -rng(it.y1, it.y2);
			else if(it.type == 1) upd(it.y1, +1);
			else ans[it.QID] += rng(it.y1, it.y2);
		}
	}
}ds;

vi ans;
vi check_validity(int _n, vi X, vi Y, vi S, vi E, vi L, vi R) {
	n = _n;
	m = X.size();
	q = S.size();

	for(int i = 0; i < m; i++) {
		if(X[i] > Y[i]) swap(X[i], Y[i]);
		UU[X[i]].push_back(Y[i]);
		DD[Y[i]].push_back(X[i]);
	}

	memset(p,-1,sizeof p);
	init();
	for(int i = 0; i < n; i++) {
		for(int v : DD[i]) {
			int par = find(v);
			if(par == i) continue;
			t[1][i].push_back(par);
			p[1][0][par] = i;
			dsu[par] = i;
		}
	}
	init();
	for(int i = n-1; i >= 0; i--) {
		for(int v : UU[i]) {
			int par = find(v);
			if(par == i) continue;
			t[0][i].push_back(par);
			p[0][0][par] = i;
			dsu[par] = i;
		}
	}
	dfs(0,0);
	dfs(n-1,1);
	for(int i = 0; i < n; i++)
		posIn1[eul[1][i]] = i;
	for(int i = 0; i < n; i++)
		ds.add_point(i, posIn1[eul[0][i]]);

	for(int id : {0,1}) 
		for(int j = 1; j < 18; j++)
			for(int i = 0; i < n; i++)
				if(p[id][j-1][i] != -1) 
					p[id][j][i] = p[id][j-1][p[id][j-1][i]];

	for(int Q = 0; Q < q; Q++) {
		int U = S[Q], V = E[Q];
		for(int j = 17; j >= 0; j--) {
			if(p[0][j][U] != -1 && L[Q] <= p[0][j][U]) U = p[0][j][U];
			if(p[1][j][V] != -1 && p[1][j][V] <= R[Q]) V = p[1][j][V];
		}
		ds.add_query(st[0][U], ft[0][U], st[1][V], ft[1][V], Q);
	}
	ds.LineSweep();
	for(int i = 0; i < q; i++)
		ans.push_back(ds.ans[i] > 0);
	return ans;
}

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