제출 #1060460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1060460		jamjanek	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4062 ms	88148 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
vector<int>graf[maxn];
int father1[maxn], father2[maxn], ojciec1[maxn], ojciec2[maxn];
int find1(int x){
	if(father1[x] == x)return x;
	return father1[x] = find1(father1[x]);
}
int find2(int x){
	if(father2[x] == x)return x;
	return father2[x] = find2(father2[x]);
}
int pre[maxn], post[maxn], preit = -1;
vector<int>graf2[maxn], graf1[maxn];

void dfs(int x){
	pre[x] = ++preit;
	for(auto j: graf1[x])
		dfs(j);
	post[x] = preit;
}

vector<int> A;

vector<pair<pair<int,int>, int>>przedzialy[maxn];

int pocz, kon, it;
void dfs2(int x){
//	printf("%d %d\n", x, graf2[x].size());
	if(pocz<=pre[x] && pre[x]<=kon)
		A[it] = 1;
	for(auto j: graf2[x])
		dfs2(j);
}

int jump1[maxn][19], jump2[maxn][19];

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 i;
	for(i=0;i<(int)X.size();i++){
		graf[Y[i]].push_back(X[i]);
		graf[X[i]].push_back(Y[i]);
	}
	for(i=0;i<n;i++)
		ojciec1[i] = n, ojciec2[i] = -1, father1[i] = father2[i] = i;
	for(i=0;i<n;i++){
		for(auto j: graf[i])
			if(j<i){
				if(find1(j) != i)ojciec1[find1(j)] = i;
				father1[find1(j)] = i;
			}
	}
	for(i=n-1;i>=0;i--)
		for(auto j: graf[i])
			if(j>i){
				if(find2(j) != i)ojciec2[find2(j)] = i;
				father2[find2(j)] = i;
			}
	for(i=0;i<n;i++){
		graf1[ojciec1[i]].push_back(i);
		graf2[ojciec2[i]].push_back(i);
	}
//	for(i=0;i<n;i++)printf("%d ", ojciec1[i]);printf("\n");
//	for(i=0;i<n;i++)printf("%d ", ojciec2[i]);printf("\n");
//	return {};
	for(i=0;i<n;i++){
		jump1[i][0] = ojciec1[i];
		if(jump1[i][0] == n)jump1[i][0] = i;
	}
	for(i=0;i<n;i++){
		jump2[i][0] = ojciec2[i];
		if(jump2[i][0] == -1)jump2[i][0] = i;
	}
	for(int j=1;j<18;j++)
		for(int i=0;i<n;i++){
			jump1[i][j] = jump1[jump1[i][j-1]][j-1];
			jump2[i][j] = jump2[jump2[i][j-1]][j-1];
		}
	dfs(n);
//	for(i=0;i<n;i++)printf("%d ", pre[i]);printf("\n");
//	for(i=0;i<n;i++)printf("%d ", post[i]);printf("\n");
	int q = S.size();
	A.resize(q, 0);
	for (int i = 0; i < q; ++i) {
		if(E[i]>R[i] || S[i]<L[i])continue;
		int pom1 = E[i], pom2 = S[i];
		for(int j = 17;j>=0;j--){
//			printf("%d %d\n", pom1, pom2);
			if(jump1[pom1][j]<=R[i])
				pom1 = jump1[pom1][j];
			if(jump2[pom2][j]>=L[i])
				pom2 = jump2[pom2][j];
		}
		pocz = pre[pom1], kon = post[pom1], it = i;
		dfs2(pom2);
//		printf("%d: %d %d %d %d\n", i, pom1, pom2, pocz, kon);
//		przedzialy[pom2].push_back({{pre[pom1], post[pom1]},i});
	}
	preit = 0;
//	dfs2(n);
	return A;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51