답안 #465367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465367	2021-08-15T17:56:05 Z	dutch	늑대인간 (IOI18_werewolf)	C++17	100 / 100	1647 ms	159816 KB

werewolf

#include <bits/stdc++.h>
using namespace std;
// #include "werewolf.h"
typedef vector<int> vi;

const int NL = 2e5, ML = 6e5, LOG = 21;

int N, M, Q, k, dfsTimer;
int e[NL], r[NL], p[2][LOG][ML], st[2*NL], tL[2][ML], tR[2][ML];
vi g[ML];

int find(int u){
	return e[u] < 0 ? u : e[u] = find(e[u]);
}

void dfs(int u){
	tL[k][u] = u < N ? ++dfsTimer : 1+dfsTimer;
	for(int v : g[u]) dfs(v);
	tR[k][u] = dfsTimer;
}

vi check_validity(int __N, vi X, vi Y, vi S, vi E, vi L, vi R){
	N = __N, Q = size(S), M = size(X);
	for(int i=0; i<M; ++i)
		if(X[i] > Y[i]) swap(X[i], Y[i]);
	
	vi h(M);
	iota(begin(h), end(h), 0);

	for(; k<2; ++k){
		sort(begin(h), end(h), [&](int &u, int &v){
			return k ? X[u] > X[v] : Y[u] < Y[v];
		});
		iota(r, r+N, 0);
		fill(e, e+N,-1);

		for(int &i : h){
			int u = find(X[i]), v = find(Y[i]);

			p[k][0][r[u]] = i+N;
			p[k][0][r[v]] = i+N;

			if(e[u] > e[v]) swap(u, v);
			g[i+N] = {r[u]};
			if(u != v) g[i+N].push_back(r[v]);
			if(u != v){
				e[u] += e[v];
				e[v] = u;
			}
			r[u] = i+N;
		}

		dfsTimer = -1;
		dfs(p[k][0][h.back()+N] = h.back()+N);

		for(int i=0; i+1<LOG; ++i)
			for(int u=0; u<N+M; ++u)
				p[k][i+1][u] = p[k][i][p[k][i][u]];
	}

	vector<array<int, 3>> q(Q);

	for(int i=0; i<Q; ++i){
		int u = E[i];
		for(int j=LOG; --j>=0; )
			if(Y[p[0][j][u] - N] <= R[i]) u = p[0][j][u];
 		q[i] = {tL[0][u], tR[0][u], i};
	}

	vi byL(N), res(Q); int pt = N-1;
	iota(begin(byL), end(byL), 0);
	sort(begin(byL), end(byL), [&](int u, int v){
		return tL[0][u] < tL[0][v];
	});
	sort(rbegin(q), rend(q));

	fill(st, st+N+N, ML);
	for(auto &[lx, rx, id] : q){
		while(pt>=0 && tL[0][byL[pt]] >= lx){
			int i = tL[1][byL[pt]];
			for(st[i+=N]=tL[0][byL[pt]]; i/=2; )
				st[i] = min(st[2*i], st[2*i+1]);
			--pt;
		}
		int u = S[id];
		for(int j=LOG; --j>=0; )
			if(X[p[1][j][u] - N] >= L[id]) u = p[1][j][u];
		
		int qL = tL[1][u], qR = tR[1][u], x = N+N;

		for(qL+=N, qR+=N+1; qL<qR; qL/=2, qR/=2){
			if(qL & 1) x = min(x, st[qL++]);
			if(qR & 1) x = min(x, st[--qR]);
		}
		res[id] = x <= rx;
	}
	return res;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	14796 KB	Output is correct
2	Correct	9 ms	14828 KB	Output is correct
3	Correct	10 ms	14796 KB	Output is correct
4	Correct	9 ms	14668 KB	Output is correct
5	Correct	9 ms	14756 KB	Output is correct
6	Correct	9 ms	14760 KB	Output is correct
7	Correct	9 ms	14796 KB	Output is correct
8	Correct	9 ms	14792 KB	Output is correct
9	Correct	9 ms	14796 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	14796 KB	Output is correct
2	Correct	9 ms	14828 KB	Output is correct
3	Correct	10 ms	14796 KB	Output is correct
4	Correct	9 ms	14668 KB	Output is correct
5	Correct	9 ms	14756 KB	Output is correct
6	Correct	9 ms	14760 KB	Output is correct
7	Correct	9 ms	14796 KB	Output is correct
8	Correct	9 ms	14792 KB	Output is correct
9	Correct	9 ms	14796 KB	Output is correct
10	Correct	16 ms	16332 KB	Output is correct
11	Correct	15 ms	16180 KB	Output is correct
12	Correct	15 ms	16204 KB	Output is correct
13	Correct	16 ms	16372 KB	Output is correct
14	Correct	14 ms	16204 KB	Output is correct
15	Correct	18 ms	16952 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	896 ms	110092 KB	Output is correct
2	Correct	1116 ms	113296 KB	Output is correct
3	Correct	976 ms	111276 KB	Output is correct
4	Correct	907 ms	110416 KB	Output is correct
5	Correct	856 ms	110312 KB	Output is correct
6	Correct	902 ms	110144 KB	Output is correct
7	Correct	839 ms	110156 KB	Output is correct
8	Correct	1083 ms	113256 KB	Output is correct
9	Correct	709 ms	111328 KB	Output is correct
10	Correct	586 ms	110324 KB	Output is correct
11	Correct	611 ms	110220 KB	Output is correct
12	Correct	622 ms	110156 KB	Output is correct
13	Correct	1159 ms	113288 KB	Output is correct
14	Correct	1149 ms	113284 KB	Output is correct
15	Correct	1157 ms	113352 KB	Output is correct
16	Correct	1237 ms	113232 KB	Output is correct
17	Correct	834 ms	110156 KB	Output is correct

Subtask #4
51.0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	14796 KB	Output is correct
2	Correct	9 ms	14828 KB	Output is correct
3	Correct	10 ms	14796 KB	Output is correct
4	Correct	9 ms	14668 KB	Output is correct
5	Correct	9 ms	14756 KB	Output is correct
6	Correct	9 ms	14760 KB	Output is correct
7	Correct	9 ms	14796 KB	Output is correct
8	Correct	9 ms	14792 KB	Output is correct
9	Correct	9 ms	14796 KB	Output is correct
10	Correct	16 ms	16332 KB	Output is correct
11	Correct	15 ms	16180 KB	Output is correct
12	Correct	15 ms	16204 KB	Output is correct
13	Correct	16 ms	16372 KB	Output is correct
14	Correct	14 ms	16204 KB	Output is correct
15	Correct	18 ms	16952 KB	Output is correct
16	Correct	896 ms	110092 KB	Output is correct
17	Correct	1116 ms	113296 KB	Output is correct
18	Correct	976 ms	111276 KB	Output is correct
19	Correct	907 ms	110416 KB	Output is correct
20	Correct	856 ms	110312 KB	Output is correct
21	Correct	902 ms	110144 KB	Output is correct
22	Correct	839 ms	110156 KB	Output is correct
23	Correct	1083 ms	113256 KB	Output is correct
24	Correct	709 ms	111328 KB	Output is correct
25	Correct	586 ms	110324 KB	Output is correct
26	Correct	611 ms	110220 KB	Output is correct
27	Correct	622 ms	110156 KB	Output is correct
28	Correct	1159 ms	113288 KB	Output is correct
29	Correct	1149 ms	113284 KB	Output is correct
30	Correct	1157 ms	113352 KB	Output is correct
31	Correct	1237 ms	113232 KB	Output is correct
32	Correct	834 ms	110156 KB	Output is correct
33	Correct	1051 ms	110964 KB	Output is correct
34	Correct	1647 ms	129320 KB	Output is correct
35	Correct	1237 ms	117984 KB	Output is correct
36	Correct	991 ms	111804 KB	Output is correct
37	Correct	1237 ms	115172 KB	Output is correct
38	Correct	1103 ms	113744 KB	Output is correct
39	Correct	974 ms	116616 KB	Output is correct
40	Correct	1522 ms	159816 KB	Output is correct
41	Correct	890 ms	113468 KB	Output is correct
42	Correct	663 ms	111828 KB	Output is correct
43	Correct	1450 ms	139812 KB	Output is correct
44	Correct	1041 ms	115044 KB	Output is correct
45	Correct	786 ms	119032 KB	Output is correct
46	Correct	815 ms	116676 KB	Output is correct
47	Correct	1173 ms	114628 KB	Output is correct
48	Correct	1163 ms	113436 KB	Output is correct
49	Correct	1179 ms	114468 KB	Output is correct
50	Correct	1219 ms	113352 KB	Output is correct
51	Correct	1523 ms	159464 KB	Output is correct
52	Correct	1481 ms	159428 KB	Output is correct

답안 #465367

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