제출 #766057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766057		Nonoze	Werewolf (IOI18_werewolf)	C++17	34 / 100	452 ms	51624 KiB

werewolf

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

struct node
{
	node* left, *right;
	int mini, maxi;
	void update() {
		mini=min(left->mini, right->mini);
		maxi=max(left->maxi, right->maxi);
	}
};

int querymin(node* root, int left, int right, int qLeft, int qRight, int val)
{
	if (left>qRight || right<qLeft) return -1;
	if (left==right) return (root->mini<val?left:-1);

	int mid=(left+right)/2;
	if (left>=qLeft && right<=qRight) {
		if (root->left->mini<val)
		{
			return querymin(root->left, left, mid, qLeft, qRight, val);
		}
		if (root->right->mini<val)
		{
			return querymin(root->right, mid+1, right, qLeft, qRight, val);
		}
		return -1;
	}
	int s1=querymin(root->left, left, mid, qLeft, qRight, val);
	if (s1!=-1) return s1;
	return querymin(root->right, mid+1, right, qLeft, qRight, val);
}

int querymax(node* root, int left, int right, int qLeft, int qRight, int val)
{
	if (left>qRight || right<qLeft) return -1;
	if (left==right) return (root->maxi>val?left:-1);
	int mid=(left+right)/2;
	if (left>=qLeft && right<=qRight) {
		if (root->right->maxi>val)
		{
			return querymax(root->right, mid+1, right, qLeft, qRight, val);
		}
		if (root->left->maxi>val)
		{
			return querymax(root->left, left, mid, qLeft, qRight, val);
		}
		return -1;
	}
	int s1=querymax(root->right, mid+1, right, qLeft, qRight, val);
	if (s1!=-1) return s1;
	return querymax(root->left, left, mid, qLeft, qRight, val);
}

void build(node* root, int left, int right, vector<int>& v)
{
	if (left==right) {
		root->mini=root->maxi=v[left];
		return;
	}

	root->left=new node{NULL, NULL, (int)v.size(), 0};
	root->right=new node{NULL, NULL, (int)v.size(), 0};

	int mid=(left+right)/2;
	build(root->left, left, mid, v);
	build(root->right, mid+1, right, v);
	root->update();
	return;
}

void destroy(node *root) {
	if (root->left) destroy(root->left);
	if (root->right) destroy(root->right);
	delete root;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int Q = S.size();
	vector<int> A(Q);
	vector<int> cities;
	vector<int> empl(N);
	vector<bool> verif(N, false);
	vector<int> adj[N];
	for (int i = 0; i < (int)X.size(); ++i)
	{
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	int curr=-1;
	for (int i = 0; i < N; ++i)
	{
		if (adj[i].size()==1)
		{
			curr=i;
			break;
		}
	}
	for (int i = 0; i < N; ++i)
	{
		cities.push_back(curr);
		empl[curr]=i;
		if (adj[adj[curr][0]][0]==curr && adj[adj[curr][0]].size()>=2)
		{
			swap(adj[adj[curr][0]][0], adj[adj[curr][0]][1]);
		}
		curr=adj[curr][0];
	}


	node *root=new node{NULL, NULL, N, 0};
	node *root2=new node{NULL, NULL, N, 0};
	build(root, 0, N-1, cities);
	reverse(cities.begin(), cities.end());
	build(root2, 0, N-1, cities);
	for (int i = 0; i < Q; ++i) {
		int human=-1;
		int wolf=-1;
		E[i]=empl[E[i]];
		S[i]=empl[S[i]];
		if (E[i]<S[i])
		{
			S[i]=N-S[i]-1;
			E[i]=N-E[i]-1;
			human=querymax(root2, 0, N-1, S[i], E[i], R[i]);
			wolf=querymin(root2, 0, N-1, S[i], E[i], L[i]);
		} else {
			human=querymax(root, 0, N-1, S[i], E[i], R[i]);
			wolf=querymin(root, 0, N-1, S[i], E[i], L[i]);
		}
		if (human==-1) {
			if (wolf==-1 || wolf>S[i]) {
				A[i]=1;
			} else {
				A[i]=0;
			}
		} else if (wolf==-1) {
			if (human<E[i]) {
				A[i]=1;
			} else {
				A[i]=0;
			}
		}
		else if (human+1<wolf) {
			A[i]=1;
		} else A[i]=0;
	}
	return A;
}

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