oj.uz

답안 #766183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766183 2023-06-25T11:08:06 Z Nonoze 늑대인간 (IOI18_werewolf) C++17
0 / 100
 4000 ms 34744 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
//Subtask 1+2

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(), M=X.size();
	vector<int> A(Q, 0);
	vector<int> adj[N];
	for (int i = 0; i < M; ++i)
	{
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	for (int i = 0; i < Q; ++i)
	{
		queue<pair<int, bool>> q;
		map<pair<int, bool>, bool> visited;
		q.push({S[i], 0});
		while(!q.empty()) {
			int x=q.front().first;
			bool boolean=q.front().second;
			q.pop();
			if (visited.count({x, boolean}) || (x<L[i] && boolean==0) || (x<R[i] && boolean==1)) continue;
			if (x==E[i] && boolean==1)
			{
				A[i]=1;
				break;
			}
			visited[{x, boolean}]=true;
			for (auto u: adj[x]) {
				if (u>=L[i] && u<=R[i] && !boolean) q.push({u, 1});
				q.push({u, boolean});
			}
		}
	}
	return A;
}

//Subtask 3
/***********************
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4056 ms 34744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -