oj.uz

Submission #340282

# Submission time Handle Problem Language Result Execution time Memory
340282 2020-12-27T11:30:27 Z nikatamliani Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 100572 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];
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;
}
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); 
	int Q = S.size();
	vi A(Q);
	vi seen(N);
	for(int i = 0; i < Q; ++i) {
		int s = up(S[i], L[i], 0);
		int e = up(E[i], R[i], 1);
		for(int x = in[0][s]; x <= out[0][s]; ++x) {//slow af
			seen[arr[0][x]] = 1;
		}
		for(int x = in[1][e]; x <= out[1][e]; ++x) {
			if(seen[arr[1][x]]) {
				A[i] = 1;
				break;
			}
		}
		for(int x = in[0][s]; x <= out[0][s]; ++x) {
			seen[arr[0][x]] = 0;
		}
	}
	return A;
}

Compilation message

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:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0; i < X.size(); ++i) {
      |                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28652 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct
3 Correct 20 ms 28524 KB Output is correct
4 Correct 19 ms 28524 KB Output is correct
5 Correct 20 ms 28524 KB Output is correct
6 Correct 20 ms 28524 KB Output is correct
7 Correct 20 ms 28524 KB Output is correct
8 Correct 19 ms 28524 KB Output is correct
9 Correct 20 ms 28524 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28652 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct
3 Correct 20 ms 28524 KB Output is correct
4 Correct 19 ms 28524 KB Output is correct
5 Correct 20 ms 28524 KB Output is correct
6 Correct 20 ms 28524 KB Output is correct
7 Correct 20 ms 28524 KB Output is correct
8 Correct 19 ms 28524 KB Output is correct
9 Correct 20 ms 28524 KB Output is correct
10 Correct 49 ms 29676 KB Output is correct
11 Correct 43 ms 29676 KB Output is correct
12 Correct 26 ms 29548 KB Output is correct
13 Correct 38 ms 29804 KB Output is correct
14 Correct 27 ms 29804 KB Output is correct
15 Correct 45 ms 29676 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 974 ms 96224 KB Output is correct
2 Execution timed out 4075 ms 100572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28652 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct
3 Correct 20 ms 28524 KB Output is correct
4 Correct 19 ms 28524 KB Output is correct
5 Correct 20 ms 28524 KB Output is correct
6 Correct 20 ms 28524 KB Output is correct
7 Correct 20 ms 28524 KB Output is correct
8 Correct 19 ms 28524 KB Output is correct
9 Correct 20 ms 28524 KB Output is correct
10 Correct 49 ms 29676 KB Output is correct
11 Correct 43 ms 29676 KB Output is correct
12 Correct 26 ms 29548 KB Output is correct
13 Correct 38 ms 29804 KB Output is correct
14 Correct 27 ms 29804 KB Output is correct
15 Correct 45 ms 29676 KB Output is correct
16 Correct 974 ms 96224 KB Output is correct
17 Execution timed out 4075 ms 100572 KB Time limit exceeded
18 Halted 0 ms 0 KB -