답안 #75296 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75296	2018-09-09T06:59:18 Z	gs14004	늑대인간 (IOI18_werewolf)	C++17	100 / 100	749 ms	68604 KB

werewolf

#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

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	21240 KB	Output is correct
2	Correct	20 ms	21364 KB	Output is correct
3	Correct	19 ms	21468 KB	Output is correct
4	Correct	19 ms	21468 KB	Output is correct
5	Correct	19 ms	21468 KB	Output is correct
6	Correct	21 ms	21468 KB	Output is correct
7	Correct	24 ms	21468 KB	Output is correct
8	Correct	20 ms	21468 KB	Output is correct
9	Correct	20 ms	21468 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	21240 KB	Output is correct
2	Correct	20 ms	21364 KB	Output is correct
3	Correct	19 ms	21468 KB	Output is correct
4	Correct	19 ms	21468 KB	Output is correct
5	Correct	19 ms	21468 KB	Output is correct
6	Correct	21 ms	21468 KB	Output is correct
7	Correct	24 ms	21468 KB	Output is correct
8	Correct	20 ms	21468 KB	Output is correct
9	Correct	20 ms	21468 KB	Output is correct
10	Correct	26 ms	22008 KB	Output is correct
11	Correct	26 ms	22052 KB	Output is correct
12	Correct	26 ms	22164 KB	Output is correct
13	Correct	29 ms	22252 KB	Output is correct
14	Correct	27 ms	22252 KB	Output is correct
15	Correct	27 ms	22296 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	627 ms	61540 KB	Output is correct
2	Correct	553 ms	64140 KB	Output is correct
3	Correct	532 ms	64140 KB	Output is correct
4	Correct	613 ms	64140 KB	Output is correct
5	Correct	542 ms	64140 KB	Output is correct
6	Correct	570 ms	64140 KB	Output is correct
7	Correct	585 ms	64140 KB	Output is correct
8	Correct	517 ms	64140 KB	Output is correct
9	Correct	467 ms	64140 KB	Output is correct
10	Correct	503 ms	64140 KB	Output is correct
11	Correct	505 ms	64140 KB	Output is correct
12	Correct	548 ms	64140 KB	Output is correct
13	Correct	532 ms	64252 KB	Output is correct
14	Correct	558 ms	64252 KB	Output is correct
15	Correct	548 ms	64252 KB	Output is correct
16	Correct	547 ms	64252 KB	Output is correct
17	Correct	561 ms	64252 KB	Output is correct

Subtask #4
51.0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	21240 KB	Output is correct
2	Correct	20 ms	21364 KB	Output is correct
3	Correct	19 ms	21468 KB	Output is correct
4	Correct	19 ms	21468 KB	Output is correct
5	Correct	19 ms	21468 KB	Output is correct
6	Correct	21 ms	21468 KB	Output is correct
7	Correct	24 ms	21468 KB	Output is correct
8	Correct	20 ms	21468 KB	Output is correct
9	Correct	20 ms	21468 KB	Output is correct
10	Correct	26 ms	22008 KB	Output is correct
11	Correct	26 ms	22052 KB	Output is correct
12	Correct	26 ms	22164 KB	Output is correct
13	Correct	29 ms	22252 KB	Output is correct
14	Correct	27 ms	22252 KB	Output is correct
15	Correct	27 ms	22296 KB	Output is correct
16	Correct	627 ms	61540 KB	Output is correct
17	Correct	553 ms	64140 KB	Output is correct
18	Correct	532 ms	64140 KB	Output is correct
19	Correct	613 ms	64140 KB	Output is correct
20	Correct	542 ms	64140 KB	Output is correct
21	Correct	570 ms	64140 KB	Output is correct
22	Correct	585 ms	64140 KB	Output is correct
23	Correct	517 ms	64140 KB	Output is correct
24	Correct	467 ms	64140 KB	Output is correct
25	Correct	503 ms	64140 KB	Output is correct
26	Correct	505 ms	64140 KB	Output is correct
27	Correct	548 ms	64140 KB	Output is correct
28	Correct	532 ms	64252 KB	Output is correct
29	Correct	558 ms	64252 KB	Output is correct
30	Correct	548 ms	64252 KB	Output is correct
31	Correct	547 ms	64252 KB	Output is correct
32	Correct	561 ms	64252 KB	Output is correct
33	Correct	646 ms	64252 KB	Output is correct
34	Correct	416 ms	64252 KB	Output is correct
35	Correct	643 ms	64252 KB	Output is correct
36	Correct	608 ms	64252 KB	Output is correct
37	Correct	647 ms	64252 KB	Output is correct
38	Correct	644 ms	64252 KB	Output is correct
39	Correct	625 ms	66848 KB	Output is correct
40	Correct	749 ms	68372 KB	Output is correct
41	Correct	608 ms	68372 KB	Output is correct
42	Correct	553 ms	68372 KB	Output is correct
43	Correct	705 ms	68372 KB	Output is correct
44	Correct	626 ms	68372 KB	Output is correct
45	Correct	584 ms	68372 KB	Output is correct
46	Correct	578 ms	68372 KB	Output is correct
47	Correct	586 ms	68372 KB	Output is correct
48	Correct	573 ms	68372 KB	Output is correct
49	Correct	575 ms	68372 KB	Output is correct
50	Correct	539 ms	68372 KB	Output is correct
51	Correct	721 ms	68512 KB	Output is correct
52	Correct	697 ms	68604 KB	Output is correct

답안 #75296

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 8.0 / 8.0

Subtask #3 34.0 / 34.0

Subtask #4 51.0 / 51.0

Subtask #1
7.0 / 7.0

Subtask #2
8.0 / 8.0

Subtask #3
34.0 / 34.0

Subtask #4
51.0 / 51.0