oj.uz

Submission #102700

# Submission time Handle Problem Language Result Execution time Memory
102700 2019-03-27T02:32:56 Z bert30702 Werewolf (IOI18_werewolf) C++17
100 / 100
 2834 ms 165872 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int MX = 2e5 + 100;
vector<int> G[MX], G_mx[MX], G_mn[MX];
int boss_mx[MX], boss_mn[MX];
int l_mx[MX], r_mx[MX], l_mn[MX], r_mn[MX], tmp[MX];
vector<int> ptr_mn[MX], ptr_mx[MX];
vector<int> T[MX * 4];
void build_ptr_mn(int u, int p, int &ptr) {
	l_mn[u] = ++ptr;
	tmp[ptr] = u;
	if(p != -1) {
		ptr_mn[u].push_back(p);
		while(ptr_mn[ptr_mn[u].back()].size() >= ptr_mn[u].size()) {
			ptr_mn[u].push_back(ptr_mn[ptr_mn[u].back()][ptr_mn[u].size() - 1]);
		}
	}
	for(auto it: G_mn[u]) build_ptr_mn(it, u, ptr);
	r_mn[u] = ptr;
}
void build_ptr_mx(int u, int p, int &ptr) {
	l_mx[u] = ++ptr;
	if(p != -1) {
		ptr_mx[u].push_back(p);
		while(ptr_mx[ptr_mx[u].back()].size() >= ptr_mx[u].size()) {
			ptr_mx[u].push_back(ptr_mx[ptr_mx[u].back()][ptr_mx[u].size() - 1]);
		}
	}
	for(auto it: G_mx[u]) build_ptr_mx(it, u, ptr);
	r_mx[u] = ptr;
}
void build_T(int u, int l, int r) {
	if(l == r) return T[u] = {l_mx[tmp[l]]}, void();
	int m = l + r >> 1;
	build_T(u * 2 + 1,     l, m);
	build_T(u * 2 + 2, m + 1, r);
	T[u].resize(r - l + 1);
	merge(T[u * 2 + 1].begin(), T[u * 2 + 1].end(), T[u * 2 + 2].begin(), T[u * 2 + 2].end(), T[u].begin());
}
int query_T(int u, int l, int r, int s, int t, int a, int b) {
	if(l == s and r == t) return lower_bound(T[u].begin(), T[u].end(), a) != upper_bound(T[u].begin(), T[u].end(), b);
	int m = l + r >> 1;
	if(t <= m) return query_T(u * 2 + 1,     l, m, s, t, a, b);
	if(s >  m) return query_T(u * 2 + 2, m + 1, r, s, t, a, b);
	return query_T(u * 2 + 1, l, m, s, m, a, b) | query_T(u * 2 + 2, m + 1, r, m + 1, t, a, b);
}
vector<int> query(int N, vector<int> S, vector<int> T, vector<int> L, vector<int> R) {
	vector<int> ans;
	for(int i = 0; i < S.size(); i ++) {
		for(int j = 2000; j >= 0; j --) {
			if(ptr_mn[S[i]].empty()) break;
			j = min(j, (int) ptr_mn[S[i]].size() - 1);
			if(ptr_mn[S[i]][j] >= L[i]) S[i] = ptr_mn[S[i]][j];
		}
		for(int j = 2000; j >= 0; j --) {
			if(ptr_mx[T[i]].empty()) break;
			j = min(j, (int) ptr_mx[T[i]].size() - 1);
			if(ptr_mx[T[i]][j] <= R[i]) T[i] = ptr_mx[T[i]][j];
		}
		ans.push_back(query_T(0, 1, N, l_mn[S[i]], r_mn[S[i]], l_mx[T[i]], r_mx[T[i]]));
	}
	return ans;
}
int Find_mx(int u) {
	return boss_mx[u] == u ? u : boss_mx[u] = Find_mx(boss_mx[u]);
}
int Find_mn(int u) {
	return boss_mn[u] == u ? u : boss_mn[u] = Find_mn(boss_mn[u]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> T, vector<int> L, vector<int> R) {
	for(int i = 0; i < N; i ++) boss_mx[i] = boss_mn[i] = i;
	for(int i = 0; i < X.size(); i ++) {
		G[X[i]].push_back(Y[i]);
		G[Y[i]].push_back(X[i]);
	}
	for(int i = N - 1; i >= 0; i --) {
		for(auto it: G[i]) {
			if(it > i and Find_mn(it) != i) {
				G_mn[i].push_back(Find_mn(it));
				boss_mn[Find_mn(it)] = i;
			}
		}
	}
	for(int i = 0; i < N; i ++) {
		for(auto it: G[i]) {
			if(it < i and Find_mx(it) != i) {
				G_mx[i].push_back(Find_mx(it));
				boss_mx[Find_mx(it)] = i;
			}
		}
	}
	int ptr_mn = 0; build_ptr_mn(0    , -1, ptr_mn);
	int ptr_mx = 0; build_ptr_mx(N - 1, -1, ptr_mx);
	build_T(0, 1, N);
	return query(N, S, T, L, R);
}

Compilation message

werewolf.cpp: In function 'void build_T(int, int, int)':
werewolf.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
werewolf.cpp: In function 'int query_T(int, int, int, int, int, int, int)':
werewolf.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
werewolf.cpp: In function 'std::vector<int> query(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i ++) {
                 ~~^~~~~~~~~~
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:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i ++) {
                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 42872 KB Output is correct
2 Correct 44 ms 42744 KB Output is correct
3 Correct 49 ms 42744 KB Output is correct
4 Correct 43 ms 42616 KB Output is correct
5 Correct 44 ms 42744 KB Output is correct
6 Correct 42 ms 42616 KB Output is correct
7 Correct 43 ms 42616 KB Output is correct
8 Correct 41 ms 42724 KB Output is correct
9 Correct 41 ms 42804 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 42872 KB Output is correct
2 Correct 44 ms 42744 KB Output is correct
3 Correct 49 ms 42744 KB Output is correct
4 Correct 43 ms 42616 KB Output is correct
5 Correct 44 ms 42744 KB Output is correct
6 Correct 42 ms 42616 KB Output is correct
7 Correct 43 ms 42616 KB Output is correct
8 Correct 41 ms 42724 KB Output is correct
9 Correct 41 ms 42804 KB Output is correct
10 Correct 51 ms 44152 KB Output is correct
11 Correct 54 ms 44152 KB Output is correct
12 Correct 49 ms 43768 KB Output is correct
13 Correct 55 ms 44284 KB Output is correct
14 Correct 60 ms 44156 KB Output is correct
15 Correct 57 ms 44152 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1455 ms 126972 KB Output is correct
2 Correct 2544 ms 147184 KB Output is correct
3 Correct 1901 ms 141104 KB Output is correct
4 Correct 1386 ms 133564 KB Output is correct
5 Correct 1305 ms 133352 KB Output is correct
6 Correct 1286 ms 131392 KB Output is correct
7 Correct 1271 ms 126740 KB Output is correct
8 Correct 2520 ms 147080 KB Output is correct
9 Correct 1268 ms 140948 KB Output is correct
10 Correct 954 ms 133680 KB Output is correct
11 Correct 1076 ms 133364 KB Output is correct
12 Correct 912 ms 131684 KB Output is correct
13 Correct 2145 ms 160648 KB Output is correct
14 Correct 2045 ms 160772 KB Output is correct
15 Correct 2112 ms 160724 KB Output is correct
16 Correct 2129 ms 160752 KB Output is correct
17 Correct 1113 ms 126832 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 42872 KB Output is correct
2 Correct 44 ms 42744 KB Output is correct
3 Correct 49 ms 42744 KB Output is correct
4 Correct 43 ms 42616 KB Output is correct
5 Correct 44 ms 42744 KB Output is correct
6 Correct 42 ms 42616 KB Output is correct
7 Correct 43 ms 42616 KB Output is correct
8 Correct 41 ms 42724 KB Output is correct
9 Correct 41 ms 42804 KB Output is correct
10 Correct 51 ms 44152 KB Output is correct
11 Correct 54 ms 44152 KB Output is correct
12 Correct 49 ms 43768 KB Output is correct
13 Correct 55 ms 44284 KB Output is correct
14 Correct 60 ms 44156 KB Output is correct
15 Correct 57 ms 44152 KB Output is correct
16 Correct 1455 ms 126972 KB Output is correct
17 Correct 2544 ms 147184 KB Output is correct
18 Correct 1901 ms 141104 KB Output is correct
19 Correct 1386 ms 133564 KB Output is correct
20 Correct 1305 ms 133352 KB Output is correct
21 Correct 1286 ms 131392 KB Output is correct
22 Correct 1271 ms 126740 KB Output is correct
23 Correct 2520 ms 147080 KB Output is correct
24 Correct 1268 ms 140948 KB Output is correct
25 Correct 954 ms 133680 KB Output is correct
26 Correct 1076 ms 133364 KB Output is correct
27 Correct 912 ms 131684 KB Output is correct
28 Correct 2145 ms 160648 KB Output is correct
29 Correct 2045 ms 160772 KB Output is correct
30 Correct 2112 ms 160724 KB Output is correct
31 Correct 2129 ms 160752 KB Output is correct
32 Correct 1113 ms 126832 KB Output is correct
33 Correct 1855 ms 141224 KB Output is correct
34 Correct 455 ms 77724 KB Output is correct
35 Correct 2399 ms 145136 KB Output is correct
36 Correct 1554 ms 141056 KB Output is correct
37 Correct 2418 ms 143984 KB Output is correct
38 Correct 2126 ms 141904 KB Output is correct
39 Correct 1783 ms 164620 KB Output is correct
40 Correct 2203 ms 152252 KB Output is correct
41 Correct 1777 ms 143108 KB Output is correct
42 Correct 1387 ms 141056 KB Output is correct
43 Correct 2834 ms 164752 KB Output is correct
44 Correct 2189 ms 144024 KB Output is correct
45 Correct 1603 ms 165872 KB Output is correct
46 Correct 2086 ms 164644 KB Output is correct
47 Correct 2326 ms 161024 KB Output is correct
48 Correct 2239 ms 160752 KB Output is correct
49 Correct 2404 ms 160840 KB Output is correct
50 Correct 2141 ms 160764 KB Output is correct
51 Correct 1852 ms 152252 KB Output is correct
52 Correct 1816 ms 152284 KB Output is correct