제출 #1060465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1060465		jamjanek	늑대인간 (IOI18_werewolf)	C++14	100 / 100	475 ms	131832 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;
}




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

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

const int base = 1<<18;
vector<int>tree[2*base];

void dodaj(int w, int l, int p, int a, int b, int index){
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		tree[w].push_back(index);
		return;
	}
	dodaj(w*2, l, (l+p)/2, a, b, index);
	dodaj(w*2+1, (l+p)/2+1, p, a, b, index);
}

void usun(int x){
	x+=base;
	while(x>0){
		while(tree[x].size()){
			if(ustawione[tree[x].back()]==1)tree[x].pop_back();
			else{
				A[tree[x].back()] = 1;
				ustawione[tree[x].back()] = 1;
				tree[x].pop_back();
			}
		}
		x/=2;
	}
}

void dfs2(int x){
	for(auto j: przedzialy[x]){
		dodaj(1, 0, base-1, j.first.first, j.first.second, j.second);
	}
	usun(pre[x]);
	
	for(auto j: graf2[x])
		dfs2(j);
	for(auto j: przedzialy[x]){
		ustawione[j.second] = 1;
	}

}



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;
	for(i=0;i<n;i++)
		if(ojciec2[i]==-1)
			dfs2(i);
	return A;
}

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