oj.uz

Submission #340279

# Submission time Handle Problem Language Result Execution time Memory
340279 2020-12-27T11:28:09 Z nikatamliani Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 108380 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
const int NAX = 4e5+10, LG = 20;
vi 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);
	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]; !A[i] && x <= out[0][s]; ++x) {
			for(int y = in[1][e]; !A[i] && y <= out[1][e]; ++y) {
				if(arr[0][x] == arr[1][y]) {
					A[i] = 1;
				}
			}
		}
	}
	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 17 ms 28652 KB Output is correct
3 Correct 17 ms 28524 KB Output is correct
4 Correct 17 ms 28524 KB Output is correct
5 Correct 20 ms 28652 KB Output is correct
6 Correct 18 ms 28652 KB Output is correct
7 Correct 19 ms 28652 KB Output is correct
8 Correct 19 ms 28652 KB Output is correct
9 Correct 18 ms 28652 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 17 ms 28652 KB Output is correct
3 Correct 17 ms 28524 KB Output is correct
4 Correct 17 ms 28524 KB Output is correct
5 Correct 20 ms 28652 KB Output is correct
6 Correct 18 ms 28652 KB Output is correct
7 Correct 19 ms 28652 KB Output is correct
8 Correct 19 ms 28652 KB Output is correct
9 Correct 18 ms 28652 KB Output is correct
10 Correct 28 ms 29804 KB Output is correct
11 Correct 31 ms 29804 KB Output is correct
12 Correct 27 ms 29676 KB Output is correct
13 Correct 27 ms 29932 KB Output is correct
14 Correct 27 ms 29932 KB Output is correct
15 Correct 1380 ms 29864 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2146 ms 103776 KB Output is correct
2 Execution timed out 4046 ms 108380 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 17 ms 28652 KB Output is correct
3 Correct 17 ms 28524 KB Output is correct
4 Correct 17 ms 28524 KB Output is correct
5 Correct 20 ms 28652 KB Output is correct
6 Correct 18 ms 28652 KB Output is correct
7 Correct 19 ms 28652 KB Output is correct
8 Correct 19 ms 28652 KB Output is correct
9 Correct 18 ms 28652 KB Output is correct
10 Correct 28 ms 29804 KB Output is correct
11 Correct 31 ms 29804 KB Output is correct
12 Correct 27 ms 29676 KB Output is correct
13 Correct 27 ms 29932 KB Output is correct
14 Correct 27 ms 29932 KB Output is correct
15 Correct 1380 ms 29864 KB Output is correct
16 Correct 2146 ms 103776 KB Output is correct
17 Execution timed out 4046 ms 108380 KB Time limit exceeded
18 Halted 0 ms 0 KB -