oj.uz

Submission #114121

# Submission time Handle Problem Language Result Execution time Memory
114121 2019-05-30T12:41:48 Z arman_ferdous Werewolf (IOI18_werewolf) C++17
100 / 100
 995 ms 112244 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47352 KB Output is correct
2 Correct 41 ms 47352 KB Output is correct
3 Correct 41 ms 47356 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 41 ms 47352 KB Output is correct
6 Correct 40 ms 47360 KB Output is correct
7 Correct 39 ms 47360 KB Output is correct
8 Correct 41 ms 47320 KB Output is correct
9 Correct 61 ms 47480 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47352 KB Output is correct
2 Correct 41 ms 47352 KB Output is correct
3 Correct 41 ms 47356 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 41 ms 47352 KB Output is correct
6 Correct 40 ms 47360 KB Output is correct
7 Correct 39 ms 47360 KB Output is correct
8 Correct 41 ms 47320 KB Output is correct
9 Correct 61 ms 47480 KB Output is correct
10 Correct 46 ms 48332 KB Output is correct
11 Correct 46 ms 48356 KB Output is correct
12 Correct 45 ms 48368 KB Output is correct
13 Correct 47 ms 48356 KB Output is correct
14 Correct 46 ms 48352 KB Output is correct
15 Correct 48 ms 48480 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 100908 KB Output is correct
2 Correct 843 ms 102996 KB Output is correct
3 Correct 802 ms 101708 KB Output is correct
4 Correct 792 ms 101072 KB Output is correct
5 Correct 756 ms 101108 KB Output is correct
6 Correct 799 ms 101028 KB Output is correct
7 Correct 725 ms 100808 KB Output is correct
8 Correct 812 ms 103088 KB Output is correct
9 Correct 657 ms 101724 KB Output is correct
10 Correct 581 ms 101140 KB Output is correct
11 Correct 609 ms 101040 KB Output is correct
12 Correct 624 ms 101108 KB Output is correct
13 Correct 873 ms 112208 KB Output is correct
14 Correct 867 ms 112188 KB Output is correct
15 Correct 875 ms 112208 KB Output is correct
16 Correct 849 ms 111948 KB Output is correct
17 Correct 724 ms 100840 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47352 KB Output is correct
2 Correct 41 ms 47352 KB Output is correct
3 Correct 41 ms 47356 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 41 ms 47352 KB Output is correct
6 Correct 40 ms 47360 KB Output is correct
7 Correct 39 ms 47360 KB Output is correct
8 Correct 41 ms 47320 KB Output is correct
9 Correct 61 ms 47480 KB Output is correct
10 Correct 46 ms 48332 KB Output is correct
11 Correct 46 ms 48356 KB Output is correct
12 Correct 45 ms 48368 KB Output is correct
13 Correct 47 ms 48356 KB Output is correct
14 Correct 46 ms 48352 KB Output is correct
15 Correct 48 ms 48480 KB Output is correct
16 Correct 799 ms 100908 KB Output is correct
17 Correct 843 ms 102996 KB Output is correct
18 Correct 802 ms 101708 KB Output is correct
19 Correct 792 ms 101072 KB Output is correct
20 Correct 756 ms 101108 KB Output is correct
21 Correct 799 ms 101028 KB Output is correct
22 Correct 725 ms 100808 KB Output is correct
23 Correct 812 ms 103088 KB Output is correct
24 Correct 657 ms 101724 KB Output is correct
25 Correct 581 ms 101140 KB Output is correct
26 Correct 609 ms 101040 KB Output is correct
27 Correct 624 ms 101108 KB Output is correct
28 Correct 873 ms 112208 KB Output is correct
29 Correct 867 ms 112188 KB Output is correct
30 Correct 875 ms 112208 KB Output is correct
31 Correct 849 ms 111948 KB Output is correct
32 Correct 724 ms 100840 KB Output is correct
33 Correct 798 ms 100284 KB Output is correct
34 Correct 369 ms 75220 KB Output is correct
35 Correct 923 ms 102368 KB Output is correct
36 Correct 833 ms 101540 KB Output is correct
37 Correct 886 ms 101760 KB Output is correct
38 Correct 807 ms 101960 KB Output is correct
39 Correct 869 ms 108816 KB Output is correct
40 Correct 957 ms 108748 KB Output is correct
41 Correct 783 ms 101248 KB Output is correct
42 Correct 652 ms 101328 KB Output is correct
43 Correct 995 ms 106832 KB Output is correct
44 Correct 795 ms 101604 KB Output is correct
45 Correct 712 ms 109108 KB Output is correct
46 Correct 753 ms 108748 KB Output is correct
47 Correct 882 ms 112244 KB Output is correct
48 Correct 906 ms 112064 KB Output is correct
49 Correct 860 ms 112208 KB Output is correct
50 Correct 922 ms 111956 KB Output is correct
51 Correct 896 ms 108040 KB Output is correct
52 Correct 909 ms 108012 KB Output is correct