oj.uz

Submission #456482

# Submission time Handle Problem Language Result Execution time Memory
456482 2021-08-06T22:26:16 Z flappybird Werewolf (IOI18_werewolf) C++14
100 / 100
 2016 ms 162880 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define MAX 401010
#define MAXS 18
#define INF 1010101010
ll N, M;
vector<ll> X, Y, S, E, L, R;
ll prt1[MAX], prt2[MAX]; //tree
ll val1[MAX], val2[MAX]; //tree
ll ord1[MAX], ord2[MAX]; //tree
ll l1[MAX], l2[MAX]; //tree
ll r1[MAX], r2[MAX]; //tree
ll sp1[MAX][MAXS], sp2[MAX][MAXS];
pair<ll, ll> range1[MAX], range2[MAX];
vector<ll> adj[MAX];
struct dsu {
	vector<ll> p;
	dsu() {}
	dsu(ll n) {
		N = n;
		p.clear();
		p.resize(N);
		ll i;
		for (i = 0; i < N; i++) p[i] = i;
	}
	ll find(ll x) {
		if (p[x] == x) return x;
		return p[x] = find(p[x]);
	}
	void uni(ll u, ll v) {
		u = find(u);
		v = find(v);
		if (u == v) return;
		p.push_back(p.size());
		p[v] = p[u] = p.size() - 1;
	}
};
//merge_sort_segtree %$%#%#%$
struct segtree {
	ll N, s;
	vector<vector<ll>> tree;
	vector<ll> l, r;
	ll get(vector<ll>& v, ll l, ll r) {
		return upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
	}
	void init(ll x = 1) {
		if (x >= s) {
			if (!tree[x].empty()) sort(tree[x].begin(), tree[x].end());
			l[x] = r[x] = x - s;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
		tree[x] = tree[x * 2];
		for (auto v : tree[x * 2 + 1]) tree[x].push_back(v);
		sort(tree[x].begin(), tree[x].end());
	}
	segtree() {}
	segtree(ll _N) {
		N = _N;
		s = 1 << (ll)ceil(log2(N));
		tree.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
	}
	ll query(ll low, ll high, ll s, ll e, ll loc = 1) {
		if (low == l[loc] && high == r[loc]) return get(tree[loc], s, e);
		if (high <= r[loc * 2]) return query(low, high, s, e, loc * 2);
		if (low >= l[loc * 2 + 1]) return query(low, high, s, e, loc * 2 + 1);
		return query(low, r[loc * 2], s, e, loc * 2) | query(l[loc * 2 + 1], high, s, e, loc * 2 + 1);
	}
};
void make_tree(ll mode = 0) {
	ll i;
	dsu d = dsu(N);
	if (!mode) {
		for (i = 0; i < 2 * N - 1; i++) l1[i] = r1[i] = -1;
		for (i = 0; i < N; i++) {
			for (auto v : adj[i]) {
				if (v > i) continue;
				if (d.find(v) == d.find(i)) continue;
				ll ii, vv;
				ii = d.find(i);
				vv = d.find(v);
				d.uni(ii, vv);
				val1[d.p.size() - 1] = i;
				l1[d.p.size() - 1] = ii;
				r1[d.p.size() - 1] = vv;
				prt1[ii] = prt1[vv] = d.p.size() - 1;
			}
		}
	}
	else {
		for (i = 0; i < 2 * N - 1; i++) l2[i] = r2[i] = -1;
		for (i = N - 1; i >= 0; i--) {
			for (auto v : adj[i]) {
				if (i > v) continue;
				if (d.find(v) == d.find(i)) continue;
				ll ii, vv;
				ii = d.find(i);
				vv = d.find(v);
				d.uni(i, v);
				val2[d.p.size() - 1] = i;
				l2[d.p.size() - 1] = ii;
				r2[d.p.size() - 1] = vv;
				prt2[ii] = prt2[vv] = d.p.size() - 1;
			}
		}
	}
}
ll cnt;
//rev_ord
void dfs1(ll x) {
	if (x < N) {
		ord1[x] = cnt++;
		range1[x] = { ord1[x], ord1[x] };
		return;
	}
	dfs1(l1[x]);
	dfs1(r1[x]);
	range1[x] = { range1[l1[x]].first, range1[r1[x]].second };
}
void dfs2(ll x) {
	if (x < N) {
		ord2[x] = cnt++;
		range2[x] = { ord2[x], ord2[x] };
		return;
	}
	dfs2(l2[x]);
	dfs2(r2[x]);
	range2[x] = { range2[l2[x]].first, range2[r2[x]].second };
}
std::vector<int> check_validity(int _N, vector<int> _X, vector<int> _Y, vector<int> _S, vector<int> _E, vector<int> _L, vector<int> _R) {
	tie(N, X, Y, S, E, L, R) = make_tuple(_N, _X, _Y, _S, _E, _L, _R);
	vector<ll> ret;
	ll i;
	M = X.size();
	for (i = 0; i < M; i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
	make_tree(0);
	make_tree(1);
	prt1[2 * N - 2] = prt2[2 * N - 2] = 2 * N - 2;
	dfs1(2 * N - 2);
	cnt = 0;
	dfs2(2 * N - 2);
	ll Q = S.size();
	segtree mseg;
	mseg = segtree(N);
	for (i = 0; i <= 2 * N - 2; i++) sp1[i][0] = prt1[i];
	for (i = 0; i <= 2 * N - 2; i++) sp2[i][0] = prt2[i];
	for (ll k = 1; k < MAXS; k++) {
		for (i = 0; i <= 2 * N - 2; i++) {
			sp1[i][k] = sp1[sp1[i][k - 1]][k - 1];
			sp2[i][k] = sp2[sp2[i][k - 1]][k - 1];
		}
	}
	for (i = 0; i < N; i++) mseg.tree[mseg.s + ord1[i]].push_back(ord2[i]);
	mseg.init();
	for (i = 0; i < Q; i++) {
		ll s, e, l, r;
		s = S[i];
		e = E[i];
		l = L[i];
		r = R[i];
		ll v = e;
		for (ll k = MAXS - 1; k >= 0; k--) if (val1[sp1[v][k]] <= r) v = sp1[v][k];
		pair<ll, ll> wolf = range1[v];
		v = s;
		for (ll k = MAXS - 1; k >= 0; k--) if (val2[sp2[v][k]] >= l) v = sp2[v][k];
		pair<ll, ll> human = range2[v];
		if (mseg.query(wolf.first, wolf.second, human.first, human.second)) ret.push_back(1);
		else ret.push_back(0);
	}
	return ret;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9804 KB Output is correct
2 Correct 6 ms 9804 KB Output is correct
3 Correct 7 ms 9804 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Correct 6 ms 9876 KB Output is correct
6 Correct 6 ms 9804 KB Output is correct
7 Correct 6 ms 9804 KB Output is correct
8 Correct 6 ms 9804 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9804 KB Output is correct
2 Correct 6 ms 9804 KB Output is correct
3 Correct 7 ms 9804 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Correct 6 ms 9876 KB Output is correct
6 Correct 6 ms 9804 KB Output is correct
7 Correct 6 ms 9804 KB Output is correct
8 Correct 6 ms 9804 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 15 ms 11852 KB Output is correct
11 Correct 16 ms 11896 KB Output is correct
12 Correct 13 ms 11852 KB Output is correct
13 Correct 16 ms 12028 KB Output is correct
14 Correct 16 ms 11980 KB Output is correct
15 Correct 19 ms 12076 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 997 ms 148164 KB Output is correct
2 Correct 1769 ms 156928 KB Output is correct
3 Correct 1612 ms 154652 KB Output is correct
4 Correct 1377 ms 153756 KB Output is correct
5 Correct 1320 ms 153736 KB Output is correct
6 Correct 1221 ms 153632 KB Output is correct
7 Correct 978 ms 153580 KB Output is correct
8 Correct 1646 ms 156716 KB Output is correct
9 Correct 1277 ms 154692 KB Output is correct
10 Correct 786 ms 154964 KB Output is correct
11 Correct 773 ms 154848 KB Output is correct
12 Correct 977 ms 154796 KB Output is correct
13 Correct 1465 ms 157972 KB Output is correct
14 Correct 1508 ms 157848 KB Output is correct
15 Correct 1498 ms 157804 KB Output is correct
16 Correct 1445 ms 157912 KB Output is correct
17 Correct 1006 ms 154768 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9804 KB Output is correct
2 Correct 6 ms 9804 KB Output is correct
3 Correct 7 ms 9804 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Correct 6 ms 9876 KB Output is correct
6 Correct 6 ms 9804 KB Output is correct
7 Correct 6 ms 9804 KB Output is correct
8 Correct 6 ms 9804 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 15 ms 11852 KB Output is correct
11 Correct 16 ms 11896 KB Output is correct
12 Correct 13 ms 11852 KB Output is correct
13 Correct 16 ms 12028 KB Output is correct
14 Correct 16 ms 11980 KB Output is correct
15 Correct 19 ms 12076 KB Output is correct
16 Correct 997 ms 148164 KB Output is correct
17 Correct 1769 ms 156928 KB Output is correct
18 Correct 1612 ms 154652 KB Output is correct
19 Correct 1377 ms 153756 KB Output is correct
20 Correct 1320 ms 153736 KB Output is correct
21 Correct 1221 ms 153632 KB Output is correct
22 Correct 978 ms 153580 KB Output is correct
23 Correct 1646 ms 156716 KB Output is correct
24 Correct 1277 ms 154692 KB Output is correct
25 Correct 786 ms 154964 KB Output is correct
26 Correct 773 ms 154848 KB Output is correct
27 Correct 977 ms 154796 KB Output is correct
28 Correct 1465 ms 157972 KB Output is correct
29 Correct 1508 ms 157848 KB Output is correct
30 Correct 1498 ms 157804 KB Output is correct
31 Correct 1445 ms 157912 KB Output is correct
32 Correct 1006 ms 154768 KB Output is correct
33 Correct 1512 ms 155804 KB Output is correct
34 Correct 433 ms 43588 KB Output is correct
35 Correct 2016 ms 158120 KB Output is correct
36 Correct 1369 ms 155220 KB Output is correct
37 Correct 1857 ms 157480 KB Output is correct
38 Correct 1513 ms 155744 KB Output is correct
39 Correct 1714 ms 161180 KB Output is correct
40 Correct 1394 ms 162284 KB Output is correct
41 Correct 1364 ms 156956 KB Output is correct
42 Correct 816 ms 155212 KB Output is correct
43 Correct 1988 ms 160652 KB Output is correct
44 Correct 1661 ms 157476 KB Output is correct
45 Correct 1361 ms 161500 KB Output is correct
46 Correct 1523 ms 161248 KB Output is correct
47 Correct 1396 ms 157904 KB Output is correct
48 Correct 1403 ms 157824 KB Output is correct
49 Correct 1396 ms 158012 KB Output is correct
50 Correct 1372 ms 157824 KB Output is correct
51 Correct 1148 ms 162880 KB Output is correct
52 Correct 1153 ms 162764 KB Output is correct