답안 #76689 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76689	2018-09-15T19:21:35 Z	tincamatei	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1270 ms	107128 KB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

const int MAX_N = 200000;
const int MAX_Q = 200000;

std::vector<int> graph[MAX_N], graph1[MAX_N], graph2[MAX_N];
std::vector<int> queryId[MAX_N];
int par1[20][MAX_N+1], par2[20][MAX_N+1];
int entryT[MAX_N], exitT[MAX_N];
int top, eulertour[1+MAX_N], poz[1+MAX_N];
int subarb[1+MAX_N];
int aib[1+MAX_N];
int sef1[MAX_N], sef2[MAX_N];
bool bl1[MAX_N], bl2[MAX_N];

static inline int lsb(int x) {
	return x & (-x);
}

void updateAib(int poz, int val) {
	while(poz <= MAX_N) {
		aib[poz] += val;
		poz += lsb(poz);
	}
}

int queryAib(int poz) {
	int rez = 0;
	while(poz > 0) {
		rez += aib[poz];
		poz -= lsb(poz);
	}
	return rez;
}

struct Query {
	int a, b, rez;
} query[MAX_Q];

void calcBinaryLifting(int n) {
	for(int l = 1; l < 20; ++l)
		for(int i = 0; i < n; ++i) {
			par1[l][i] = par1[l - 1][par1[l - 1][i]];
			par2[l][i] = par2[l - 1][par2[l - 1][i]];
		}
}

int searchSmaller(int src, int val) {
	for(int l = 19; l >= 0; --l) {
		int jump = par1[l][src];
		if(jump != MAX_N && jump <= val)
			src = jump;
	}
	return src;
}

int searchGreater(int src, int val) {
	for(int l = 19; l >= 0; --l) {
		int jump = par2[l][src];
		if(jump != MAX_N && jump >= val)
			src = jump;
	}
	return src;
}

void dfs(int nod) {
	entryT[nod] = top + 1;
	for(auto it: graph1[nod])
		dfs(it);
	poz[nod] = ++top;
	eulertour[top] = nod;
	exitT[nod] = top;
}

void dfs2(int nod) {
	subarb[nod] = 1;
	for(auto it: graph2[nod]) {
		dfs2(it);
		subarb[nod] += subarb[it];
	}
}

void dfs3(int nod, int val = 0) {
	int heavySon = -1, heavySize = 0;
	for(auto it: graph2[nod])
		if(subarb[it] > heavySize) {
			heavySize = subarb[it];
			heavySon = it;
		}
	
	if(val == 0) {
		for(auto it: graph2[nod])
			if(it != heavySon) {
				dfs3(it, val);
				dfs3(it, -1);
			}
		if(heavySon != -1)
			dfs3(heavySon, 0);
		for(auto it: graph2[nod])
			if(it != heavySon)
				dfs3(it, 1);
		
		updateAib(poz[nod], 1);
		
		for(auto it: queryId[nod]) {
			if(queryAib(exitT[query[it].a]) - queryAib(entryT[query[it].a] - 1) > 0)
				query[it].rez = 1;
		}
	} else {
		for(auto it: graph2[nod])
			dfs3(it, val);
		updateAib(poz[nod], val);
	}
}

int myfind(int x, int *sef) {
	if(x == sef[x])
		return x;
	else {
		sef[x] = myfind(sef[x], sef);
		return sef[x];
	}
}

void myunion(int a, int b, int *sef, bool doMin = true) {
	int sa = myfind(a, sef), sb = myfind(b, sef);

	if((doMin && sa < sb) || (!doMin && sa > sb))
		sef[sb] = sa;
	else
		sef[sa] = sb;
}

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 Q = S.size(), M = X.size();
	std::vector<int> A(Q);
	
	for(int i = 0; i < M; ++i) {
		graph[X[i]].push_back(Y[i]);
		graph[Y[i]].push_back(X[i]);
	}
	
	for(int l = 0; l < 20; ++l)
		par1[l][MAX_N] = par2[l][MAX_N] = MAX_N;
	
	for(int i = 0; i < N; ++i)
		sef1[i] = sef2[i] = i;

	for(int i = 0; i < N; ++i) {
		par1[0][i] = par2[0][i] = MAX_N;
		for(auto it: graph[i])
			if(it < i && myfind(i, sef1) != myfind(it, sef1)) {
				par1[0][myfind(it, sef1)] = i;
				graph1[i].push_back(myfind(it, sef1));
				myunion(i, it, sef1, false);
			}
	}
	
	for(int i = N - 1; i >= 0; --i) 
		for(auto it: graph[i])
			if(it > i && myfind(i, sef2) != myfind(it, sef2)) {
				par2[0][myfind(it, sef2)] = i;
				graph2[i].push_back(myfind(it, sef2));
				myunion(i, it, sef2);
			}
	
	calcBinaryLifting(N);
	dfs(N - 1);
	dfs2(0);
	for(int i = 0; i < Q; ++i) {
		query[i].a = searchSmaller(E[i], R[i]);
		query[i].b = searchGreater(S[i], L[i]);
		queryId[query[i].b].push_back(i);
	}

	dfs3(0);

	for(int i = 0; i < Q; ++i)
		A[i] = query[i].rez;
	return A;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	19448 KB	Output is correct
2	Correct	19 ms	19452 KB	Output is correct
3	Correct	19 ms	19512 KB	Output is correct
4	Correct	19 ms	19512 KB	Output is correct
5	Correct	19 ms	19512 KB	Output is correct
6	Correct	20 ms	19552 KB	Output is correct
7	Correct	19 ms	19552 KB	Output is correct
8	Correct	18 ms	19552 KB	Output is correct
9	Correct	18 ms	19552 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	19448 KB	Output is correct
2	Correct	19 ms	19452 KB	Output is correct
3	Correct	19 ms	19512 KB	Output is correct
4	Correct	19 ms	19512 KB	Output is correct
5	Correct	19 ms	19512 KB	Output is correct
6	Correct	20 ms	19552 KB	Output is correct
7	Correct	19 ms	19552 KB	Output is correct
8	Correct	18 ms	19552 KB	Output is correct
9	Correct	18 ms	19552 KB	Output is correct
10	Correct	26 ms	20600 KB	Output is correct
11	Correct	28 ms	20600 KB	Output is correct
12	Correct	28 ms	20616 KB	Output is correct
13	Correct	26 ms	20744 KB	Output is correct
14	Correct	26 ms	20760 KB	Output is correct
15	Correct	34 ms	20760 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1114 ms	87148 KB	Output is correct
2	Correct	1026 ms	89340 KB	Output is correct
3	Correct	932 ms	89340 KB	Output is correct
4	Correct	886 ms	89340 KB	Output is correct
5	Correct	965 ms	89340 KB	Output is correct
6	Correct	1083 ms	89340 KB	Output is correct
7	Correct	1131 ms	89340 KB	Output is correct
8	Correct	1000 ms	89340 KB	Output is correct
9	Correct	657 ms	89340 KB	Output is correct
10	Correct	677 ms	89340 KB	Output is correct
11	Correct	773 ms	89340 KB	Output is correct
12	Correct	791 ms	89340 KB	Output is correct
13	Correct	1126 ms	99308 KB	Output is correct
14	Correct	1250 ms	99308 KB	Output is correct
15	Correct	1110 ms	99308 KB	Output is correct
16	Correct	1230 ms	99308 KB	Output is correct
17	Correct	1041 ms	99308 KB	Output is correct

Subtask #4
51.0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	19448 KB	Output is correct
2	Correct	19 ms	19452 KB	Output is correct
3	Correct	19 ms	19512 KB	Output is correct
4	Correct	19 ms	19512 KB	Output is correct
5	Correct	19 ms	19512 KB	Output is correct
6	Correct	20 ms	19552 KB	Output is correct
7	Correct	19 ms	19552 KB	Output is correct
8	Correct	18 ms	19552 KB	Output is correct
9	Correct	18 ms	19552 KB	Output is correct
10	Correct	26 ms	20600 KB	Output is correct
11	Correct	28 ms	20600 KB	Output is correct
12	Correct	28 ms	20616 KB	Output is correct
13	Correct	26 ms	20744 KB	Output is correct
14	Correct	26 ms	20760 KB	Output is correct
15	Correct	34 ms	20760 KB	Output is correct
16	Correct	1114 ms	87148 KB	Output is correct
17	Correct	1026 ms	89340 KB	Output is correct
18	Correct	932 ms	89340 KB	Output is correct
19	Correct	886 ms	89340 KB	Output is correct
20	Correct	965 ms	89340 KB	Output is correct
21	Correct	1083 ms	89340 KB	Output is correct
22	Correct	1131 ms	89340 KB	Output is correct
23	Correct	1000 ms	89340 KB	Output is correct
24	Correct	657 ms	89340 KB	Output is correct
25	Correct	677 ms	89340 KB	Output is correct
26	Correct	773 ms	89340 KB	Output is correct
27	Correct	791 ms	89340 KB	Output is correct
28	Correct	1126 ms	99308 KB	Output is correct
29	Correct	1250 ms	99308 KB	Output is correct
30	Correct	1110 ms	99308 KB	Output is correct
31	Correct	1230 ms	99308 KB	Output is correct
32	Correct	1041 ms	99308 KB	Output is correct
33	Correct	1169 ms	99308 KB	Output is correct
34	Correct	422 ms	99308 KB	Output is correct
35	Correct	1253 ms	99308 KB	Output is correct
36	Correct	1270 ms	99308 KB	Output is correct
37	Correct	1153 ms	99308 KB	Output is correct
38	Correct	1150 ms	99308 KB	Output is correct
39	Correct	1099 ms	99308 KB	Output is correct
40	Correct	1014 ms	99308 KB	Output is correct
41	Correct	802 ms	99308 KB	Output is correct
42	Correct	710 ms	99308 KB	Output is correct
43	Correct	1058 ms	99308 KB	Output is correct
44	Correct	952 ms	99308 KB	Output is correct
45	Correct	823 ms	99308 KB	Output is correct
46	Correct	919 ms	99308 KB	Output is correct
47	Correct	1077 ms	99308 KB	Output is correct
48	Correct	1097 ms	102512 KB	Output is correct
49	Correct	1130 ms	107128 KB	Output is correct
50	Correct	1148 ms	107128 KB	Output is correct
51	Correct	1012 ms	107128 KB	Output is correct
52	Correct	992 ms	107128 KB	Output is correct

답안 #76689

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