oj.uz

답안 #765171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
765171 2023-06-24T09:03:45 Z ono_de206 늑대인간 (IOI18_werewolf) C++14
100 / 100
 466 ms 89412 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 2e5 + 10;
int p[mxn], in[2][mxn], out[2][mxn], T;

int find(int x) {
	return p[x] == x ? x : p[x] = find(p[x]);
}

vector<vector<int>> adj[2], g;
vector<int> order[2];

void unite(int x, int y, int id) {
	x = find(x);
	y = find(y);
	if(x == y) return;
	p[y] = x;
	adj[id][x].pb(y);
}

void dfs(int to, int id) {
	in[id][to] = T++;
	order[id].pb(to);
	for(int x : adj[id][to]) {
		dfs(x, id);
	}
	out[id][to] = T - 1;
}

int d[mxn * 4];

void update(int l, int r, int i, int id, int x) {
	if(l == r) {
		d[i] = x;
		return;
	}
	int m = (l + r) / 2;
	if(id <= m) update(l, m, i * 2, id, x);
	else update(m + 1, r, i * 2 + 1, id, x);
	d[i] = min(d[i * 2], d[i * 2 + 1]);
}

int query(int l, int r, int i, int x, int y) {
	if(l >= x && r <= y) return d[i];
	int m = (l + r) / 2;
	if(y <= m) return query(l, m, i * 2, x, y);
	if(x > m) return query(m + 1, r, i * 2 + 1, x, y);
	return min(query(l, m, i * 2, x, y), query(m + 1, r, i * 2 + 1, x, y));
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int Q = E.size();
	vector<int> ret(Q);

	g = adj[0] = adj[1] = vector<vector<int>>(n);

	for(int i = 0; i < X.size(); i++) {
		g[X[i]].pb(Y[i]);
		g[Y[i]].pb(X[i]);
	}

	vector<int> pa(Q), pb(Q);
	vector<vector<int>> v;

	auto setDsu = [&]() -> void {
		v.clear();
		v.resize(n);
		for(int i = 0; i < n; i++) {
			p[i] = i;
		}
	};

	setDsu();
	{
		for(int i = 0; i < Q; i++) {
			v[L[i]].pb(i);
		}

		for(int i = n - 1; i >= 0; i--) {
			for(int x : g[i]) {
				if(x > i) {
					unite(i, x, 0);
				}
			}
			for(int id : v[i]) {
				pa[id] = find(S[id]);
			}
		}
	}

	setDsu();
	{
		for(int i = 0; i < Q; i++) {
			v[R[i]].pb(i);
		}

		for(int i = 0; i < n; i++) {
			for(int x : g[i]) {
				if(x < i) {
					unite(i, x, 1);
				}
			}
			for(int id : v[i]) {
				pb[id] = find(E[id]);
			}
		}
	}

	dfs(0, 0); T = 0;
	dfs(n - 1, 1); T = 0;

	vector<vector<pair<pair<int, int>, pair<int, int>>>> qu(n);
	for(int i = 0; i < Q; i++) {
		int l1 = in[0][pa[i]], r1 = out[0][pa[i]];
		int l2 = in[1][pb[i]], r2 = out[1][pb[i]];
		qu[l1].pb({{i, r1}, {l2, r2}});
	}

	for(int i = 0; i < n; i++) {
		update(0, n - 1, 1, in[1][order[0][i]], i);
	}

	for(int i = 0; i < n; i++) {
		for(auto it : qu[i]) {
			int r = it.ff.ss, L = it.ss.ff, R = it.ss.ss, id = it.ff.ff;
			int mn = query(0, n - 1, 1, L, R);
			if(mn <= r) ret[id] = 1;
			else ret[id] = 0;
		}
		update(0, n - 1, 1, in[1][order[0][i]], n + 10);
	}
	return ret;
}

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

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 5 ms 1492 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 4 ms 1384 KB Output is correct
13 Correct 4 ms 1620 KB Output is correct
14 Correct 4 ms 1620 KB Output is correct
15 Correct 5 ms 1540 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 356 ms 74228 KB Output is correct
2 Correct 345 ms 78540 KB Output is correct
3 Correct 355 ms 75372 KB Output is correct
4 Correct 347 ms 73508 KB Output is correct
5 Correct 352 ms 73800 KB Output is correct
6 Correct 357 ms 74116 KB Output is correct
7 Correct 362 ms 72284 KB Output is correct
8 Correct 328 ms 78516 KB Output is correct
9 Correct 317 ms 76036 KB Output is correct
10 Correct 292 ms 71644 KB Output is correct
11 Correct 319 ms 71432 KB Output is correct
12 Correct 331 ms 73844 KB Output is correct
13 Correct 353 ms 84748 KB Output is correct
14 Correct 390 ms 84736 KB Output is correct
15 Correct 353 ms 84608 KB Output is correct
16 Correct 342 ms 84776 KB Output is correct
17 Correct 318 ms 72484 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 5 ms 1492 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 4 ms 1384 KB Output is correct
13 Correct 4 ms 1620 KB Output is correct
14 Correct 4 ms 1620 KB Output is correct
15 Correct 5 ms 1540 KB Output is correct
16 Correct 356 ms 74228 KB Output is correct
17 Correct 345 ms 78540 KB Output is correct
18 Correct 355 ms 75372 KB Output is correct
19 Correct 347 ms 73508 KB Output is correct
20 Correct 352 ms 73800 KB Output is correct
21 Correct 357 ms 74116 KB Output is correct
22 Correct 362 ms 72284 KB Output is correct
23 Correct 328 ms 78516 KB Output is correct
24 Correct 317 ms 76036 KB Output is correct
25 Correct 292 ms 71644 KB Output is correct
26 Correct 319 ms 71432 KB Output is correct
27 Correct 331 ms 73844 KB Output is correct
28 Correct 353 ms 84748 KB Output is correct
29 Correct 390 ms 84736 KB Output is correct
30 Correct 353 ms 84608 KB Output is correct
31 Correct 342 ms 84776 KB Output is correct
32 Correct 318 ms 72484 KB Output is correct
33 Correct 374 ms 75024 KB Output is correct
34 Correct 169 ms 38748 KB Output is correct
35 Correct 386 ms 78520 KB Output is correct
36 Correct 413 ms 75340 KB Output is correct
37 Correct 372 ms 77348 KB Output is correct
38 Correct 369 ms 75880 KB Output is correct
39 Correct 407 ms 88316 KB Output is correct
40 Correct 431 ms 84436 KB Output is correct
41 Correct 376 ms 76244 KB Output is correct
42 Correct 344 ms 75164 KB Output is correct
43 Correct 466 ms 84320 KB Output is correct
44 Correct 430 ms 77140 KB Output is correct
45 Correct 381 ms 89412 KB Output is correct
46 Correct 379 ms 88624 KB Output is correct
47 Correct 347 ms 84920 KB Output is correct
48 Correct 366 ms 85000 KB Output is correct
49 Correct 336 ms 84868 KB Output is correct
50 Correct 340 ms 84780 KB Output is correct
51 Correct 381 ms 82728 KB Output is correct
52 Correct 365 ms 82752 KB Output is correct