oj.uz

Submission #114117

# Submission time Handle Problem Language Result Execution time Memory
114117 2019-05-30T12:26:18 Z arman_ferdous Werewolf (IOI18_werewolf) C++17
100 / 100
 948 ms 122060 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB Output is correct
2 Correct 37 ms 47352 KB Output is correct
3 Correct 38 ms 47352 KB Output is correct
4 Correct 62 ms 47352 KB Output is correct
5 Correct 38 ms 47348 KB Output is correct
6 Correct 38 ms 47352 KB Output is correct
7 Correct 37 ms 47344 KB Output is correct
8 Correct 38 ms 47480 KB Output is correct
9 Correct 38 ms 47408 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB Output is correct
2 Correct 37 ms 47352 KB Output is correct
3 Correct 38 ms 47352 KB Output is correct
4 Correct 62 ms 47352 KB Output is correct
5 Correct 38 ms 47348 KB Output is correct
6 Correct 38 ms 47352 KB Output is correct
7 Correct 37 ms 47344 KB Output is correct
8 Correct 38 ms 47480 KB Output is correct
9 Correct 38 ms 47408 KB Output is correct
10 Correct 44 ms 48356 KB Output is correct
11 Correct 48 ms 48340 KB Output is correct
12 Correct 46 ms 48356 KB Output is correct
13 Correct 45 ms 48616 KB Output is correct
14 Correct 47 ms 48608 KB Output is correct
15 Correct 47 ms 48608 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 770 ms 100912 KB Output is correct
2 Correct 880 ms 106832 KB Output is correct
3 Correct 782 ms 102984 KB Output is correct
4 Correct 742 ms 101188 KB Output is correct
5 Correct 791 ms 101144 KB Output is correct
6 Correct 786 ms 101068 KB Output is correct
7 Correct 731 ms 100876 KB Output is correct
8 Correct 862 ms 106708 KB Output is correct
9 Correct 645 ms 102868 KB Output is correct
10 Correct 556 ms 101296 KB Output is correct
11 Correct 565 ms 101300 KB Output is correct
12 Correct 595 ms 101068 KB Output is correct
13 Correct 808 ms 117192 KB Output is correct
14 Correct 824 ms 117040 KB Output is correct
15 Correct 830 ms 117288 KB Output is correct
16 Correct 882 ms 117324 KB Output is correct
17 Correct 741 ms 101064 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB Output is correct
2 Correct 37 ms 47352 KB Output is correct
3 Correct 38 ms 47352 KB Output is correct
4 Correct 62 ms 47352 KB Output is correct
5 Correct 38 ms 47348 KB Output is correct
6 Correct 38 ms 47352 KB Output is correct
7 Correct 37 ms 47344 KB Output is correct
8 Correct 38 ms 47480 KB Output is correct
9 Correct 38 ms 47408 KB Output is correct
10 Correct 44 ms 48356 KB Output is correct
11 Correct 48 ms 48340 KB Output is correct
12 Correct 46 ms 48356 KB Output is correct
13 Correct 45 ms 48616 KB Output is correct
14 Correct 47 ms 48608 KB Output is correct
15 Correct 47 ms 48608 KB Output is correct
16 Correct 770 ms 100912 KB Output is correct
17 Correct 880 ms 106832 KB Output is correct
18 Correct 782 ms 102984 KB Output is correct
19 Correct 742 ms 101188 KB Output is correct
20 Correct 791 ms 101144 KB Output is correct
21 Correct 786 ms 101068 KB Output is correct
22 Correct 731 ms 100876 KB Output is correct
23 Correct 862 ms 106708 KB Output is correct
24 Correct 645 ms 102868 KB Output is correct
25 Correct 556 ms 101296 KB Output is correct
26 Correct 565 ms 101300 KB Output is correct
27 Correct 595 ms 101068 KB Output is correct
28 Correct 808 ms 117192 KB Output is correct
29 Correct 824 ms 117040 KB Output is correct
30 Correct 830 ms 117288 KB Output is correct
31 Correct 882 ms 117324 KB Output is correct
32 Correct 741 ms 101064 KB Output is correct
33 Correct 821 ms 103960 KB Output is correct
34 Correct 356 ms 78208 KB Output is correct
35 Correct 860 ms 108132 KB Output is correct
36 Correct 820 ms 105052 KB Output is correct
37 Correct 894 ms 107112 KB Output is correct
38 Correct 795 ms 105804 KB Output is correct
39 Correct 831 ms 121840 KB Output is correct
40 Correct 948 ms 113432 KB Output is correct
41 Correct 683 ms 106064 KB Output is correct
42 Correct 600 ms 104880 KB Output is correct
43 Correct 876 ms 114124 KB Output is correct
44 Correct 742 ms 106832 KB Output is correct
45 Correct 710 ms 122060 KB Output is correct
46 Correct 723 ms 121804 KB Output is correct
47 Correct 874 ms 120136 KB Output is correct
48 Correct 859 ms 119884 KB Output is correct
49 Correct 835 ms 119884 KB Output is correct
50 Correct 858 ms 119852 KB Output is correct
51 Correct 880 ms 112856 KB Output is correct
52 Correct 830 ms 112680 KB Output is correct