oj.uz

답안 #340282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
340282 2020-12-27T11:30:27 Z nikatamliani 늑대인간 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -