oj.uz

Submission #554469

# Submission time Handle Problem Language Result Execution time Memory
554469 2022-04-28T12:49:48 Z keta_tsimakuridze Werewolf (IOI18_werewolf) C++14
100 / 100
 3551 ms 393700 KB 
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int N = 4e5 + 5, inf = 1e9;
vector<int> V[2][N];
int cur[2], x[2][N], p[2][N][20], timer[2], tmin[2][N], tmout[2][N], pos[2][N], n;
int par[2][N];
vector<pii> edges;
set<int> s[4 * N];
int find(int u,int t) {
	return (par[t][u] == u ? u : par[t][u] = find(par[t][u], t));
}
void build(vector<pair<int,int> > edges, int t) {
	cur[t] = n; 
	for(int i = 1; i <= cur[t]; i++) par[t][i] = i;
	for(int i = 0; i < edges.size(); i++) {
		int u = edges[i].f, v = edges[i].s;
		if(find(u, t) != find(v, t)) {
			++cur[t]; par[t][cur[t]] = cur[t];
			V[t][cur[t]].push_back(find(u, t));
			V[t][cur[t]].push_back(find(v, t));
			x[t][cur[t]] = u;
			u = find(u, t), v = find(v, t);
			par[t][u] = cur[t];
			par[t][v] = cur[t];
			p[t][u][0] = p[t][v][0] = cur[t];
			
		}
	}
	cur[t]++; if(!t)x[t][cur[t]] = inf;
	for(int i = 1; i < cur[t]; i++) {
		if(find(i, t) == i) p[t][i][0] = cur[t], V[t][cur[t]].push_back(i);
	}
	for(int j = 1; j <= 18; j++) {
		for(int i = 1; i <= cur[t]; i++) {
			p[t][i][j] = p[t][p[t][i][j - 1]][j - 1];
		}
	}
}
void dfs(int u, int t) {
	if(u <= n) {
	tmin[t][u] = ++timer[t];
	pos[t][timer[t]] = u;
	}
	for(int i = 0; i < V[t][u].size(); i++) {
		dfs(V[t][u][i], t);
	}
	if(V[t][u].size()) tmin[t][u] = tmin[t][V[t][u][0]];
	tmout[t][u] = timer[t];
}
int get(int u,int t, int X) {
	for(int i = 18; i >= 0; i--) {
		if(!p[t][u][i]) continue;
		if(t && x[t][p[t][u][i]] >= X) u = p[t][u][i];
		else if(!t && x[t][p[t][u][i]] <= X) u = p[t][u][i];
	}
	return u;
}
void build(int u,int l,int r) {
	for(int i = l; i <= r; i++) if(pos[1][i] <= n)s[u].insert(tmin[0][pos[1][i]]);
	if(l == r) return;
	int mid = (l + r) / 2;
	build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
}
bool get(int u, int st,int en,int l,int r,int x,int y) {
	if(l > en || r < st) return 0;
	if(st <= l && r <= en) {
		if(s[u].upper_bound(x - 1) != s[u].end()) {
			if(*s[u].upper_bound(x - 1) <= y) return 1;
		}
		return 0;
	}
	int mid = (l + r) / 2;
	return get(2 * u, st, en, l, mid, x, y)|get(2 * u + 1, st, en, mid + 1, r, x, y);
}
 
std::vector<int> check_validity(int nn, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    vector<pair<int,int> > edges; n = nn;
    for(int i = 0; i < X.size(); i++) {
    	++X[i]; ++Y[i];
    	edges.push_back({max(X[i], Y[i]), min(X[i], Y[i])});
	}
	
	sort(edges.begin(), edges.end()); 
	build(edges, 0); // werewolf
	
	for(int i = 0; i < edges.size(); i++) {
		swap(edges[i].f, edges[i].s);
	}
	sort(edges.rbegin(), edges.rend());
	build(edges, 1); // human
	dfs(cur[0], 0);
 
	
	dfs(cur[1], 1);
	
	build(1, 1, timer[1]);
	vector<int> ans(S.size());
 
	for(int i = 0; i < S.size(); i++) {
		int l = L[i], r = R[i], u = S[i], v = E[i];
		++l, ++r, ++u, ++v;
		if(u < l || v > r) {
			ans[i] = 0;
		
			continue;
		}
	
		u = get(u, 1, l);
		v = get(v, 0, r); 
		ans[i] = get(1, tmin[1][u], tmout[1][u], 1, timer[1], tmin[0][v], tmout[0][v]);
		
	}
	return ans;
 
}

Compilation message

werewolf.cpp: In function 'void build(std::vector<std::pair<int, int> >, int)':
werewolf.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i = 0; i < edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 0; i < V[t][u].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:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i = 0; i < X.size(); i++) {
      |                    ~~^~~~~~~~~~
werewolf.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0; i < edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
werewolf.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(int i = 0; i < S.size(); i++) {
      |                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94312 KB Output is correct
2 Correct 54 ms 94340 KB Output is correct
3 Correct 72 ms 94272 KB Output is correct
4 Correct 53 ms 94224 KB Output is correct
5 Correct 59 ms 94284 KB Output is correct
6 Correct 46 ms 94284 KB Output is correct
7 Correct 42 ms 94304 KB Output is correct
8 Correct 49 ms 94340 KB Output is correct
9 Correct 44 ms 94284 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94312 KB Output is correct
2 Correct 54 ms 94340 KB Output is correct
3 Correct 72 ms 94272 KB Output is correct
4 Correct 53 ms 94224 KB Output is correct
5 Correct 59 ms 94284 KB Output is correct
6 Correct 46 ms 94284 KB Output is correct
7 Correct 42 ms 94304 KB Output is correct
8 Correct 49 ms 94340 KB Output is correct
9 Correct 44 ms 94284 KB Output is correct
10 Correct 54 ms 97800 KB Output is correct
11 Correct 67 ms 97752 KB Output is correct
12 Correct 60 ms 97628 KB Output is correct
13 Correct 52 ms 97880 KB Output is correct
14 Correct 67 ms 97820 KB Output is correct
15 Correct 64 ms 97728 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1534 ms 369724 KB Output is correct
2 Correct 2953 ms 377756 KB Output is correct
3 Correct 2707 ms 372720 KB Output is correct
4 Correct 1892 ms 370552 KB Output is correct
5 Correct 1850 ms 370480 KB Output is correct
6 Correct 1711 ms 370192 KB Output is correct
7 Correct 1410 ms 369992 KB Output is correct
8 Correct 2937 ms 377836 KB Output is correct
9 Correct 1703 ms 372792 KB Output is correct
10 Correct 1458 ms 370388 KB Output is correct
11 Correct 1585 ms 370076 KB Output is correct
12 Correct 1170 ms 369728 KB Output is correct
13 Correct 2370 ms 377348 KB Output is correct
14 Correct 2430 ms 377424 KB Output is correct
15 Correct 2444 ms 377268 KB Output is correct
16 Correct 2441 ms 377156 KB Output is correct
17 Correct 1400 ms 369440 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94312 KB Output is correct
2 Correct 54 ms 94340 KB Output is correct
3 Correct 72 ms 94272 KB Output is correct
4 Correct 53 ms 94224 KB Output is correct
5 Correct 59 ms 94284 KB Output is correct
6 Correct 46 ms 94284 KB Output is correct
7 Correct 42 ms 94304 KB Output is correct
8 Correct 49 ms 94340 KB Output is correct
9 Correct 44 ms 94284 KB Output is correct
10 Correct 54 ms 97800 KB Output is correct
11 Correct 67 ms 97752 KB Output is correct
12 Correct 60 ms 97628 KB Output is correct
13 Correct 52 ms 97880 KB Output is correct
14 Correct 67 ms 97820 KB Output is correct
15 Correct 64 ms 97728 KB Output is correct
16 Correct 1534 ms 369724 KB Output is correct
17 Correct 2953 ms 377756 KB Output is correct
18 Correct 2707 ms 372720 KB Output is correct
19 Correct 1892 ms 370552 KB Output is correct
20 Correct 1850 ms 370480 KB Output is correct
21 Correct 1711 ms 370192 KB Output is correct
22 Correct 1410 ms 369992 KB Output is correct
23 Correct 2937 ms 377836 KB Output is correct
24 Correct 1703 ms 372792 KB Output is correct
25 Correct 1458 ms 370388 KB Output is correct
26 Correct 1585 ms 370076 KB Output is correct
27 Correct 1170 ms 369728 KB Output is correct
28 Correct 2370 ms 377348 KB Output is correct
29 Correct 2430 ms 377424 KB Output is correct
30 Correct 2444 ms 377268 KB Output is correct
31 Correct 2441 ms 377156 KB Output is correct
32 Correct 1400 ms 369440 KB Output is correct
33 Correct 2552 ms 371380 KB Output is correct
34 Correct 467 ms 114392 KB Output is correct
35 Correct 3118 ms 376408 KB Output is correct
36 Correct 2039 ms 370660 KB Output is correct
37 Correct 3008 ms 374996 KB Output is correct
38 Correct 2355 ms 371580 KB Output is correct
39 Correct 1683 ms 384948 KB Output is correct
40 Correct 1922 ms 377872 KB Output is correct
41 Correct 2421 ms 374064 KB Output is correct
42 Correct 1564 ms 370544 KB Output is correct
43 Correct 3551 ms 380144 KB Output is correct
44 Correct 2870 ms 383576 KB Output is correct
45 Correct 2252 ms 393700 KB Output is correct
46 Correct 3117 ms 393376 KB Output is correct
47 Correct 2005 ms 385604 KB Output is correct
48 Correct 2070 ms 385472 KB Output is correct
49 Correct 2094 ms 385672 KB Output is correct
50 Correct 2037 ms 385444 KB Output is correct
51 Correct 1639 ms 385380 KB Output is correct
52 Correct 1553 ms 385080 KB Output is correct