oj.uz

Submission #766057

# Submission time Handle Problem Language Result Execution time Memory
766057 2023-06-25T09:34:39 Z Nonoze Werewolf (IOI18_werewolf) C++17
34 / 100
 452 ms 51624 KB 
#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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 48100 KB Output is correct
2 Correct 411 ms 51524 KB Output is correct
3 Correct 452 ms 51420 KB Output is correct
4 Correct 397 ms 51432 KB Output is correct
5 Correct 381 ms 51432 KB Output is correct
6 Correct 445 ms 51416 KB Output is correct
7 Correct 371 ms 51324 KB Output is correct
8 Correct 370 ms 51432 KB Output is correct
9 Correct 246 ms 51404 KB Output is correct
10 Correct 278 ms 51436 KB Output is correct
11 Correct 265 ms 51352 KB Output is correct
12 Correct 255 ms 51436 KB Output is correct
13 Correct 407 ms 51436 KB Output is correct
14 Correct 383 ms 51324 KB Output is correct
15 Correct 402 ms 51624 KB Output is correct
16 Correct 359 ms 51420 KB Output is correct
17 Correct 342 ms 51436 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -