Submission #114121

#	Time	Username	Problem	Language	Result	Execution time	Memory
114121		arman_ferdous	Werewolf (IOI18_werewolf)	C++17	100 / 100	995 ms	112244 KiB

werewolf

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#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;
}

/*
Problem : Given a graph, and queries with S, E, L, R,
find if there exist a path from S to E v_1, v_2, .... v_k such that
L <= v_1, v_2, ... v_p and v_{p+1}, ... v_k <= R [where 1 <= p <= k]

Naive Solution (15): 
Do a dfs from S maintaining the bound of L, say the set of visited nodes is U
Do another dfs from E, maintain R, let the new visited set be V
there exist a path is U and V intersect at any element.

Solution (100):
We can construct a rooted directed tree so that U forms a subtree. This can be done using
adding vertices to a dsu in the descending order of indices. Same goes for V.
basically in U, if you are at any node u, then you will always be able to reach any node in its subtree.
(you will have to lift S to a point where it cant reach anything above it, use binary jumping)

So problem is changed into finding intersection of two subtrees. We can do an euler tour and 
change it to finding intersection of two intervals in two arrays.

So now, we have two arrays A and B, and several queries of [l1,r1] [l2,r2],
find intersection in A[l1] ... A[r1] and B[l2] ... B[r2]

for each position i in A[], find the corresponding A[i] in B[], let that position be j
add a point (i, j)
Now the queries are like checking the existance of a point in (x1,y1) (x2,y2) rectangle 
[x and y's are some dfs start and end times]

This can be done using a line sweep with a BIT. 
*/

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