oj.uz

Submission #340307

# Submission time Handle Problem Language Result Execution time Memory
340307 2020-12-27T12:00:34 Z nikatamliani Werewolf (IOI18_werewolf) C++14
100 / 100
 1977 ms 179692 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
const int NAX = 4e5+10, LG = 20;
vector<int> edges[NAX], tree[2][NAX], arr[2], ids; 
int in[2][NAX], out[2][NAX], p[2][NAX], L[2][NAX][LG];
int timer;
void add_edge(int x, int y, int which) {
	tree[which][x].push_back(y);
	tree[which][y].push_back(x); 
}
int find_set(int x, int which) {
	return x == p[which][x] ? x : p[which][x] = find_set(p[which][x], which);
}
void union_sets(int x, int y, int which) {
	x = find_set(x, which);
	y = find_set(y, which);
	if(x == y) {
		return;
	}
	p[which][y] = x; 
	add_edge(x, y, which);
}
void dfs(int x, int p, int which) {
	in[which][x] = ++timer;
	L[which][x][0] = p; 
	arr[which].push_back(x);
	for(int i = 1; i < LG; ++i) {
		int up = L[which][x][i - 1];
		L[which][x][i] = ~up ? L[which][up][i - 1] : -1; 
	}
	for(int to : tree[which][x]) {
		if(to != p) {
			dfs(to, x, which); 
		}
	}
	out[which][x] = timer;
}
int up(int x, int cutoff, int p) {
	for(int i = LG - 1; i >= 0; --i) {
		if(p == 0 && ~L[p][x][i] && L[p][x][i] >= cutoff) {
			x = L[p][x][i];
		}
		if(p == 1 && ~L[p][x][i] && L[p][x][i] <= cutoff) {
			x = L[p][x][i];
		}
	}
	return x;
}
struct node {
	vi v;
	void merge(vi a, vi b) {
		v.reserve((int)a.size() + (int)b.size());
		for(int i = 0, j = 0; i < (int)a.size() || j < (int)b.size();) {
			if(i < (int)a.size() && (j == (int)b.size() || a[i] < b[j])) {
				v.push_back(a[i]);
				++i;
			} else {
				v.push_back(b[j]);
				++j;
			}
		}
	}
	int less(int x) {
		int l = 0, r = (int)v.size() - 1, ans = -1;
		while(r >= l) {
			int m = l + r >> 1;
			if(v[m] <= x) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return ans+1;
	}
} t[4*NAX];
void build(int l, int r, int p) {
	if(l == r) {
		t[p].v = {arr[1][l - 1]}; 
	} else {
		int m = l + r >> 1;
		build(l, m, p << 1);
		build(m+1, r, p << 1 | 1);  
		t[p].merge(t[p << 1].v, t[p << 1 | 1].v);
	}
}
int query(int l, int r, int L, int R, int val, int p) {
	if(l > R || L > r) {
		return 0;
	}
	if(L <= l && R >= r) {
		return t[p].less(val);
	}
	int m = l + r >> 1;
	return query(l, m, L, R, val, p << 1) + query(m+1, r, L, R, val, p << 1 | 1); 
}
vector<int> check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	for(int i = 0; i < X.size(); ++i) {
		edges[X[i]].push_back(Y[i]);
		edges[Y[i]].push_back(X[i]);
	}
	for(int i = 0; i < N; ++i) {
		p[0][i] = p[1][i] = i; 
	}
	for(int i = N - 1; i >= 0; --i) {
		for(int to : edges[i]) {
			if(to > i) {
				union_sets(i, to, 0); 
			}
		}
	}
	for(int i = 0; i < N; ++i) {
		for(int to : edges[i]) {
			if(to < i) {
				union_sets(i, to, 1);
			}
		}
	}
	timer = -1; dfs(0, -1, 0);
	timer = -1; dfs(N - 1, -1, 1);
	ids = vector<int>(N);
	for(int i = 0; i < N; ++i) {
		ids[arr[0][i]] = i; 
	} 
	for(int i = 0; i < N; ++i) {
		arr[1][i] = ids[arr[1][i]];  
	}
	build(1, N, 1);
	int Q = S.size();
	vi A(Q);
	for(int i = 0; i < Q; ++i) {
		int s = up(S[i], L[i], 0);
		int e = up(E[i], R[i], 1);
		int cnt = query(1, N, in[1][e]+1, out[1][e]+1, out[0][s], 1) - query(1, N, in[1][e]+1, out[1][e]+1, in[0][s]-1, 1); 
		A[i] = cnt > 0; 
	}
	return A;
}

Compilation message

werewolf.cpp: In member function 'int node::less(int)':
werewolf.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |    int m = l + r >> 1;
      |            ~~^~~
werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:83:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |   int m = l + r >> 1;
      |           ~~^~~
werewolf.cpp: In function 'int query(int, int, int, int, int, int)':
werewolf.cpp:96:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |  int m = l + r >> 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:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0; i < X.size(); ++i) {
      |                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 66284 KB Output is correct
2 Correct 46 ms 66156 KB Output is correct
3 Correct 45 ms 66156 KB Output is correct
4 Correct 45 ms 66156 KB Output is correct
5 Correct 44 ms 66156 KB Output is correct
6 Correct 45 ms 66156 KB Output is correct
7 Correct 46 ms 66156 KB Output is correct
8 Correct 46 ms 66284 KB Output is correct
9 Correct 45 ms 66156 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 66284 KB Output is correct
2 Correct 46 ms 66156 KB Output is correct
3 Correct 45 ms 66156 KB Output is correct
4 Correct 45 ms 66156 KB Output is correct
5 Correct 44 ms 66156 KB Output is correct
6 Correct 45 ms 66156 KB Output is correct
7 Correct 46 ms 66156 KB Output is correct
8 Correct 46 ms 66284 KB Output is correct
9 Correct 45 ms 66156 KB Output is correct
10 Correct 57 ms 67564 KB Output is correct
11 Correct 55 ms 67436 KB Output is correct
12 Correct 61 ms 67436 KB Output is correct
13 Correct 55 ms 67820 KB Output is correct
14 Correct 54 ms 67708 KB Output is correct
15 Correct 54 ms 67564 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 158044 KB Output is correct
2 Correct 1618 ms 162784 KB Output is correct
3 Correct 1530 ms 167928 KB Output is correct
4 Correct 1358 ms 166648 KB Output is correct
5 Correct 1357 ms 166496 KB Output is correct
6 Correct 1223 ms 166476 KB Output is correct
7 Correct 1031 ms 166240 KB Output is correct
8 Correct 1582 ms 171008 KB Output is correct
9 Correct 1215 ms 167776 KB Output is correct
10 Correct 768 ms 166496 KB Output is correct
11 Correct 800 ms 166368 KB Output is correct
12 Correct 1033 ms 166368 KB Output is correct
13 Correct 1291 ms 172512 KB Output is correct
14 Correct 1268 ms 172512 KB Output is correct
15 Correct 1288 ms 172484 KB Output is correct
16 Correct 1245 ms 172540 KB Output is correct
17 Correct 1064 ms 166368 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 66284 KB Output is correct
2 Correct 46 ms 66156 KB Output is correct
3 Correct 45 ms 66156 KB Output is correct
4 Correct 45 ms 66156 KB Output is correct
5 Correct 44 ms 66156 KB Output is correct
6 Correct 45 ms 66156 KB Output is correct
7 Correct 46 ms 66156 KB Output is correct
8 Correct 46 ms 66284 KB Output is correct
9 Correct 45 ms 66156 KB Output is correct
10 Correct 57 ms 67564 KB Output is correct
11 Correct 55 ms 67436 KB Output is correct
12 Correct 61 ms 67436 KB Output is correct
13 Correct 55 ms 67820 KB Output is correct
14 Correct 54 ms 67708 KB Output is correct
15 Correct 54 ms 67564 KB Output is correct
16 Correct 1077 ms 158044 KB Output is correct
17 Correct 1618 ms 162784 KB Output is correct
18 Correct 1530 ms 167928 KB Output is correct
19 Correct 1358 ms 166648 KB Output is correct
20 Correct 1357 ms 166496 KB Output is correct
21 Correct 1223 ms 166476 KB Output is correct
22 Correct 1031 ms 166240 KB Output is correct
23 Correct 1582 ms 171008 KB Output is correct
24 Correct 1215 ms 167776 KB Output is correct
25 Correct 768 ms 166496 KB Output is correct
26 Correct 800 ms 166368 KB Output is correct
27 Correct 1033 ms 166368 KB Output is correct
28 Correct 1291 ms 172512 KB Output is correct
29 Correct 1268 ms 172512 KB Output is correct
30 Correct 1288 ms 172484 KB Output is correct
31 Correct 1245 ms 172540 KB Output is correct
32 Correct 1064 ms 166368 KB Output is correct
33 Correct 1411 ms 167904 KB Output is correct
34 Correct 454 ms 97776 KB Output is correct
35 Correct 1780 ms 170976 KB Output is correct
36 Correct 1353 ms 167024 KB Output is correct
37 Correct 1649 ms 170220 KB Output is correct
38 Correct 1403 ms 167940 KB Output is correct
39 Correct 1431 ms 179300 KB Output is correct
40 Correct 1344 ms 176464 KB Output is correct
41 Correct 1354 ms 169724 KB Output is correct
42 Correct 883 ms 167200 KB Output is correct
43 Correct 1977 ms 175308 KB Output is correct
44 Correct 1612 ms 170084 KB Output is correct
45 Correct 1189 ms 179692 KB Output is correct
46 Correct 1279 ms 179220 KB Output is correct
47 Correct 1269 ms 172760 KB Output is correct
48 Correct 1312 ms 172504 KB Output is correct
49 Correct 1267 ms 172640 KB Output is correct
50 Correct 1254 ms 172640 KB Output is correct
51 Correct 1217 ms 176888 KB Output is correct
52 Correct 1231 ms 177032 KB Output is correct