oj.uz

Submission #413631

# Submission time Handle Problem Language Result Execution time Memory
413631 2021-05-29T06:45:20 Z _fractal Werewolf (IOI18_werewolf) C++14
100 / 100
 1257 ms 106064 KB 
#include "werewolf.h"
#include <iostream>
using namespace std;

#define pb push_back
#define F first
#define S second

const int N = 200200;

int n;
vector<int> g[N];
vector<pair<pair<int, int>, pair<int, int>>> p[N];

struct tree {
	int t[N << 2];

	void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
		if (tl == tr)
			return t[v] = val, void();
		int tm = tl + tr >> 1;
		if (pos <= tm)
			upd(pos, val, v * 2, tl, tm);
		else
			upd(pos, val, v * 2 + 1, tm + 1, tr);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}

	int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
		if (l <= tl && tr <= r)
			return t[v];
		if (r < tl || tr < l)
			return 0;
		int tm = tl + tr >> 1;
		return max(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
	}
} t;

struct tree_dsu {
	int p[N], sz[N], root, up[20][N], LG = 18;
	int tin[N], tout[N], tick, pos[N];
	vector<int> h[N];

	int mxup(int v, int k) {
		if (v == k) return v;
		for (int i = LG; i >= 0; --i) {
			int u = up[i][v];
			if (u >= 0 && u >= k)
				v = u;
		}
		return v;
	}

	int mnup(int v, int k) {
		if (v == k) return v;
		for (int i = LG; i >= 0; --i) {
			int u = up[i][v];
			if (u >= 0 && u <= k)
				v = u;
		}
		return v;
	}

	void dfs(int v, int p = -1) {
		tin[v] = ++tick;
		pos[tick] = v;
		up[0][v] = p;
		for (int i = 1; i <= LG; ++i) {
			if (up[i - 1][v] == -1)
				up[i][v] = -1;
			else
				up[i][v] = up[i - 1][up[i - 1][v]];
		}
		for (auto to : h[v])
			dfs(to, v);
		tout[v] = tick;
	}

	void init(int n) {
		for (int i = 0; i < n; ++i)
			p[i] = i, sz[i] = 1, h[i].clear();
	}

	int get(int v) {
		return p[v] = (v == p[v] ? v : get(p[v]));
	}
	
	void unite(int v, int u) {
		if ((v = get(v)) == (u = get(u)))
			return;
		h[v].pb(u);
		root = v;
		sz[v] += sz[u];
		p[u] = v;
	}
} ds, sd;

vector<int> check_validity(int _n, vector<int> U, vector<int> V, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int q = S.size();
	int m = U.size();
	n = _n;
	int r;
	vector<int> ans(q, 0);
	ds.init(n);
	sd.init(n);
	for (int i = 0; i < m; ++i) {
		g[U[i]].pb(V[i]);
		g[V[i]].pb(U[i]);
	}
	for (int i = n - 1; i >= 0; --i) {
		for (auto to : g[i]) {
			if (to > i)
				ds.unite(i, to);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (auto to : g[i]) {
			if (to < i)
				sd.unite(i, to);
		}
	}
	ds.dfs(ds.root);
	sd.dfs(sd.root);
	for (int i = 0, l1, r1, l2, r2, v, u; i < q; ++i) {
		v = ds.mxup(S[i], L[i]);
		u = sd.mnup(E[i], R[i]);
		l1 = ds.tin[v], r1 = ds.tout[v];
		l2 = sd.tin[u], r2 = sd.tout[u];
		p[r1].pb({{i, l1}, {l2, r2}});
	}
	for (int i = 1; i <= n; ++i) {
		t.upd(sd.tin[ds.pos[i]], i);
		for (auto it : p[i]) {
			if (t.get(it.S.F, it.S.S) >= it.F.S)
				ans[it.F.F] = 1;
			else
				ans[it.F.F] = 0;
		}
	}
	return ans;
}

Compilation message

werewolf.cpp: In member function 'void tree::upd(int, int, int, int, int)':
werewolf.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
werewolf.cpp: In member function 'int tree::get(int, int, int, int, int)':
werewolf.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:102:6: warning: unused variable 'r' [-Wunused-variable]
  102 |  int r;
      |      ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19396 KB Output is correct
2 Correct 13 ms 19388 KB Output is correct
3 Correct 13 ms 19328 KB Output is correct
4 Correct 13 ms 19328 KB Output is correct
5 Correct 13 ms 19372 KB Output is correct
6 Correct 13 ms 19404 KB Output is correct
7 Correct 13 ms 19336 KB Output is correct
8 Correct 13 ms 19320 KB Output is correct
9 Correct 13 ms 19412 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19396 KB Output is correct
2 Correct 13 ms 19388 KB Output is correct
3 Correct 13 ms 19328 KB Output is correct
4 Correct 13 ms 19328 KB Output is correct
5 Correct 13 ms 19372 KB Output is correct
6 Correct 13 ms 19404 KB Output is correct
7 Correct 13 ms 19336 KB Output is correct
8 Correct 13 ms 19320 KB Output is correct
9 Correct 13 ms 19412 KB Output is correct
10 Correct 21 ms 20524 KB Output is correct
11 Correct 20 ms 20556 KB Output is correct
12 Correct 19 ms 20456 KB Output is correct
13 Correct 22 ms 20556 KB Output is correct
14 Correct 20 ms 20556 KB Output is correct
15 Correct 21 ms 20556 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1254 ms 95132 KB Output is correct
2 Correct 1035 ms 99076 KB Output is correct
3 Correct 957 ms 95632 KB Output is correct
4 Correct 1038 ms 94352 KB Output is correct
5 Correct 1004 ms 94360 KB Output is correct
6 Correct 1148 ms 95116 KB Output is correct
7 Correct 1035 ms 93992 KB Output is correct
8 Correct 879 ms 97356 KB Output is correct
9 Correct 632 ms 94848 KB Output is correct
10 Correct 521 ms 94296 KB Output is correct
11 Correct 556 ms 94048 KB Output is correct
12 Correct 629 ms 93872 KB Output is correct
13 Correct 949 ms 100764 KB Output is correct
14 Correct 981 ms 100896 KB Output is correct
15 Correct 933 ms 100852 KB Output is correct
16 Correct 937 ms 100852 KB Output is correct
17 Correct 1000 ms 93860 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19396 KB Output is correct
2 Correct 13 ms 19388 KB Output is correct
3 Correct 13 ms 19328 KB Output is correct
4 Correct 13 ms 19328 KB Output is correct
5 Correct 13 ms 19372 KB Output is correct
6 Correct 13 ms 19404 KB Output is correct
7 Correct 13 ms 19336 KB Output is correct
8 Correct 13 ms 19320 KB Output is correct
9 Correct 13 ms 19412 KB Output is correct
10 Correct 21 ms 20524 KB Output is correct
11 Correct 20 ms 20556 KB Output is correct
12 Correct 19 ms 20456 KB Output is correct
13 Correct 22 ms 20556 KB Output is correct
14 Correct 20 ms 20556 KB Output is correct
15 Correct 21 ms 20556 KB Output is correct
16 Correct 1254 ms 95132 KB Output is correct
17 Correct 1035 ms 99076 KB Output is correct
18 Correct 957 ms 95632 KB Output is correct
19 Correct 1038 ms 94352 KB Output is correct
20 Correct 1004 ms 94360 KB Output is correct
21 Correct 1148 ms 95116 KB Output is correct
22 Correct 1035 ms 93992 KB Output is correct
23 Correct 879 ms 97356 KB Output is correct
24 Correct 632 ms 94848 KB Output is correct
25 Correct 521 ms 94296 KB Output is correct
26 Correct 556 ms 94048 KB Output is correct
27 Correct 629 ms 93872 KB Output is correct
28 Correct 949 ms 100764 KB Output is correct
29 Correct 981 ms 100896 KB Output is correct
30 Correct 933 ms 100852 KB Output is correct
31 Correct 937 ms 100852 KB Output is correct
32 Correct 1000 ms 93860 KB Output is correct
33 Correct 1222 ms 96960 KB Output is correct
34 Correct 343 ms 55104 KB Output is correct
35 Correct 1232 ms 98992 KB Output is correct
36 Correct 1232 ms 97216 KB Output is correct
37 Correct 1201 ms 98340 KB Output is correct
38 Correct 1257 ms 97668 KB Output is correct
39 Correct 1244 ms 104556 KB Output is correct
40 Correct 1055 ms 105712 KB Output is correct
41 Correct 853 ms 97216 KB Output is correct
42 Correct 620 ms 95724 KB Output is correct
43 Correct 1080 ms 103432 KB Output is correct
44 Correct 918 ms 98296 KB Output is correct
45 Correct 703 ms 103996 KB Output is correct
46 Correct 727 ms 104096 KB Output is correct
47 Correct 922 ms 102616 KB Output is correct
48 Correct 931 ms 102556 KB Output is correct
49 Correct 972 ms 102684 KB Output is correct
50 Correct 959 ms 102556 KB Output is correct
51 Correct 870 ms 106064 KB Output is correct
52 Correct 843 ms 106056 KB Output is correct