oj.uz

Submission #346044

# Submission time Handle Problem Language Result Execution time Memory
346044 2021-01-09T04:41:45 Z cuongdh1912 Werewolf (IOI18_werewolf) C++14
100 / 100
 618 ms 81180 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
const int MAXN = 400005;
const int MAXT = 530000;

struct seg{
	int tree[MAXT], lim;
	void init(int n){
		fill(tree, tree + MAXT, -1e9);
		for(lim = 1; lim <= n; lim <<= 1);
	}
	void add(int x, int v){
		x += lim;
		tree[x] = max(tree[x], v);
		while(x > 1){
			x >>= 1;
			tree[x] = max(tree[2*x], tree[2*x+1]);
		}
	}
	int query(int s, int e){
		s += lim;
		e += lim;
		int ret = -1e9;
		while(s < e){
			if(s%2 == 1) ret = max(ret, tree[s++]);
			if(e%2 == 0) ret = max(ret, tree[e--]);
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ret = max(ret, tree[s]);
		return ret;
	}
}seg;

struct disj{
	int pa[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p > q) swap(p, q);
		if(p == q) return 0;
		pa[p] = q; return 1;
	}
}disj;

struct graph{
	vector<int> gph[MAXN];
	int din[MAXN], dout[MAXN], piv;
	void add_edge(int p, int q){
		gph[p].push_back(q);
	}
	void dfs(int x){
		din[x] = piv;
		if(gph[x].empty()) piv++;
		for(auto &i : gph[x]) dfs(i);
		dout[x] = piv;
	}
}g1, g2;

struct queries{
	int s, l, e, r;
	int rs, re, idx;
}qr[MAXN];

struct edges{ int s, e, x; }ed[MAXN];

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
		std::vector<int> S, std::vector<int> E,
		std::vector<int> L, std::vector<int> R) {
	int M = X.size();
	int Q = S.size();
	for(int i=0; i<Q; i++) qr[i] = {S[i], L[i], E[i], R[i], -1, -1, i};
	// make first tree
	int vtx_num = N, ptr = 0;
	qr[Q].l = -1e9;
	disj.init(N * 2);
	for(int i=0; i<M; i++) ed[i] = {X[i], Y[i], min(X[i], Y[i])};
	sort(qr, qr + Q, [&](const queries &a, const queries &b){
		return a.l > b.l;
	});
	sort(ed, ed + M, [&](const edges &a, const edges &b){
		return a.x > b.x;
	});
	for(int i=0; i<=Q; i++){
		while(ptr < M && ed[ptr].x >= qr[i].l){
			int l = disj.find(ed[ptr].s);
			int r = disj.find(ed[ptr].e);
			ptr++;
			if(l == r) continue;
			disj.uni(l, vtx_num);
			disj.uni(r, vtx_num);
			g1.add_edge(vtx_num, l);
			g1.add_edge(vtx_num, r);
			vtx_num++;
		}
		qr[i].rs = disj.find(qr[i].s);
	}
	// make second tree
	vtx_num = N, ptr = 0;
	qr[Q].r = 1e9;
	disj.init(N * 2);
	for(int i=0; i<M; i++) ed[i] = {X[i], Y[i], max(X[i], Y[i])};
	sort(qr, qr + Q, [&](const queries &a, const queries &b){
		return a.r < b.r;
	});
	sort(ed, ed + M, [&](const edges &a, const edges &b){
		return a.x < b.x;
	});
	for(int i=0; i<=Q; i++){
		while(ptr < M && ed[ptr].x <= qr[i].r){
			int l = disj.find(ed[ptr].s);
			int r = disj.find(ed[ptr].e);
			ptr++;
			if(l == r) continue;
			disj.uni(l, vtx_num);
			disj.uni(r, vtx_num);
			g2.add_edge(vtx_num, l);
			g2.add_edge(vtx_num, r);
			vtx_num++;
		}
		qr[i].re = disj.find(qr[i].e);
	}
	// both done
	g1.dfs(2 * N - 2);
	g2.dfs(2 * N - 2);
	vector<pi> points;
	vector<int> ans(Q);
	for(int i=0; i<N; i++) points.emplace_back(g1.din[i], g2.din[i]);
	sort(points.begin(), points.end());
	sort(qr, qr + Q, [&](const queries &a, const queries &b){
		return g1.dout[a.rs] < g1.dout[b.rs];
	});
	seg.init(N);
	ptr = 0;
	for(int i=0; i<Q; i++){
		while(ptr < N && points[ptr].first < g1.dout[qr[i].rs]){
			seg.add(points[ptr].second, points[ptr].first);
			ptr++;
		}
		if(seg.query(g2.din[qr[i].re], g2.dout[qr[i].re] - 1) >= g1.din[qr[i].rs]){
			ans[qr[i].idx] = 1;
		}
	}
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21228 KB Output is correct
2 Correct 13 ms 21228 KB Output is correct
3 Correct 13 ms 21228 KB Output is correct
4 Correct 13 ms 21248 KB Output is correct
5 Correct 13 ms 21248 KB Output is correct
6 Correct 16 ms 21228 KB Output is correct
7 Correct 13 ms 21228 KB Output is correct
8 Correct 13 ms 21228 KB Output is correct
9 Correct 13 ms 21228 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21228 KB Output is correct
2 Correct 13 ms 21228 KB Output is correct
3 Correct 13 ms 21228 KB Output is correct
4 Correct 13 ms 21248 KB Output is correct
5 Correct 13 ms 21248 KB Output is correct
6 Correct 16 ms 21228 KB Output is correct
7 Correct 13 ms 21228 KB Output is correct
8 Correct 13 ms 21228 KB Output is correct
9 Correct 13 ms 21228 KB Output is correct
10 Correct 18 ms 22124 KB Output is correct
11 Correct 20 ms 22124 KB Output is correct
12 Correct 19 ms 21996 KB Output is correct
13 Correct 19 ms 22124 KB Output is correct
14 Correct 18 ms 22124 KB Output is correct
15 Correct 20 ms 22144 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 69676 KB Output is correct
2 Correct 469 ms 74464 KB Output is correct
3 Correct 474 ms 71520 KB Output is correct
4 Correct 481 ms 69984 KB Output is correct
5 Correct 500 ms 70160 KB Output is correct
6 Correct 506 ms 69728 KB Output is correct
7 Correct 512 ms 69856 KB Output is correct
8 Correct 463 ms 74444 KB Output is correct
9 Correct 435 ms 71392 KB Output is correct
10 Correct 428 ms 69984 KB Output is correct
11 Correct 439 ms 69984 KB Output is correct
12 Correct 482 ms 69876 KB Output is correct
13 Correct 485 ms 74592 KB Output is correct
14 Correct 495 ms 74592 KB Output is correct
15 Correct 477 ms 74464 KB Output is correct
16 Correct 486 ms 74464 KB Output is correct
17 Correct 519 ms 69764 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21228 KB Output is correct
2 Correct 13 ms 21228 KB Output is correct
3 Correct 13 ms 21228 KB Output is correct
4 Correct 13 ms 21248 KB Output is correct
5 Correct 13 ms 21248 KB Output is correct
6 Correct 16 ms 21228 KB Output is correct
7 Correct 13 ms 21228 KB Output is correct
8 Correct 13 ms 21228 KB Output is correct
9 Correct 13 ms 21228 KB Output is correct
10 Correct 18 ms 22124 KB Output is correct
11 Correct 20 ms 22124 KB Output is correct
12 Correct 19 ms 21996 KB Output is correct
13 Correct 19 ms 22124 KB Output is correct
14 Correct 18 ms 22124 KB Output is correct
15 Correct 20 ms 22144 KB Output is correct
16 Correct 531 ms 69676 KB Output is correct
17 Correct 469 ms 74464 KB Output is correct
18 Correct 474 ms 71520 KB Output is correct
19 Correct 481 ms 69984 KB Output is correct
20 Correct 500 ms 70160 KB Output is correct
21 Correct 506 ms 69728 KB Output is correct
22 Correct 512 ms 69856 KB Output is correct
23 Correct 463 ms 74444 KB Output is correct
24 Correct 435 ms 71392 KB Output is correct
25 Correct 428 ms 69984 KB Output is correct
26 Correct 439 ms 69984 KB Output is correct
27 Correct 482 ms 69876 KB Output is correct
28 Correct 485 ms 74592 KB Output is correct
29 Correct 495 ms 74592 KB Output is correct
30 Correct 477 ms 74464 KB Output is correct
31 Correct 486 ms 74464 KB Output is correct
32 Correct 519 ms 69764 KB Output is correct
33 Correct 573 ms 70876 KB Output is correct
34 Correct 413 ms 56580 KB Output is correct
35 Correct 572 ms 74508 KB Output is correct
36 Correct 552 ms 70752 KB Output is correct
37 Correct 558 ms 73496 KB Output is correct
38 Correct 579 ms 71648 KB Output is correct
39 Correct 561 ms 79176 KB Output is correct
40 Correct 613 ms 80616 KB Output is correct
41 Correct 514 ms 72740 KB Output is correct
42 Correct 491 ms 70624 KB Output is correct
43 Correct 591 ms 79076 KB Output is correct
44 Correct 526 ms 73440 KB Output is correct
45 Correct 511 ms 79520 KB Output is correct
46 Correct 514 ms 79248 KB Output is correct
47 Correct 486 ms 74592 KB Output is correct
48 Correct 483 ms 74408 KB Output is correct
49 Correct 481 ms 74864 KB Output is correct
50 Correct 484 ms 74592 KB Output is correct
51 Correct 618 ms 81044 KB Output is correct
52 Correct 607 ms 81180 KB Output is correct