oj.uz

Submission #299677

# Submission time Handle Problem Language Result Execution time Memory
299677 2020-09-15T12:45:06 Z TMJN Werewolf (IOI18_werewolf) C++17
34 / 100
 564 ms 29932 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

vector<int>V[200000];
vector<int>A;
int treemin[1<<19],treemax[1<<19],B[200000];

int calcmin(int l,int r){
	int a=0xE869120;
	l+=(1<<18);
	r+=(1<<18);
	while(l<=r){
		a=min({a,treemin[l],treemin[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}

int calcmax(int l,int r){
	int a=0;
	l+=(1<<18);
	r+=(1<<18);
	while(l<=r){
		a=max({a,treemax[l],treemax[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}

vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
	assert(X.size()==N-1);
	for(int i=0;i<N-1;i++){
		V[X[i]].push_back(Y[i]);
		V[Y[i]].push_back(X[i]);
	}
	for(int i=0;i<N;i++){
		assert(V[i].size()<=2);
	}
	for(int i=0;i<N;i++){
		if(V[i].size()==1){
			A.push_back(i);
			A.push_back(V[i][0]);
			while(V[A.back()].size()>=2){
				for(int i=0;i<2;i++){
					if(V[A.back()][i]!=A[A.size()-2]){
						A.push_back(V[A.back()][i]);
						break;
					}
				}
			}
			break;
		}
	}
	for(int i=0;i<N;i++){
		treemin[i+(1<<18)]=treemax[i+(1<<18)]=A[i];
	}
	for(int i=(1<<18)-1;i;i--){
		treemin[i]=min(treemin[i+i],treemin[i+i+1]);
		treemax[i]=max(treemax[i+i],treemax[i+i+1]);
	}
	vector<int>res;
	int Q=S.size();
	for(int i=0;i<N;i++){
		B[A[i]]=i;
	}
	for(int i=0;i<Q;i++){
		S[i]=B[S[i]];
		E[i]=B[E[i]];
	}
	for(int i=0;i<Q;i++){
		if(S[i]<E[i]){
			int l,r;
			l=S[i];
			r=E[i]+1;
			while(l+1!=r){
				int m=(l+r)/2;
				if(calcmin(S[i],m)>=L[i]){
					l=m;
				}
				else{
					r=m;
				}
			}
			if(calcmax(l,E[i])<=R[i]){
				res.push_back(1);
			}
			else{
				res.push_back(0);
			}
		}
		else{
			int l,r;
			l=E[i];
			r=S[i]+1;
			while(l+1!=r){
				int m=(l+r)/2;
				if(calcmax(E[i],m)<=R[i]){
					l=m;
				}
				else{
					r=m;
				}
			}
			if(calcmin(l,S[i])>=L[i]){
				res.push_back(1);
			}
			else{
				res.push_back(0);
			}
		}
	}
	return res;
}

Compilation message

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from werewolf.cpp:2:
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:34:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |  assert(X.size()==N-1);
      |         ~~~~~~~~^~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 9984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 9984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 27372 KB Output is correct
2 Correct 531 ms 29804 KB Output is correct
3 Correct 536 ms 29804 KB Output is correct
4 Correct 537 ms 29676 KB Output is correct
5 Correct 526 ms 29764 KB Output is correct
6 Correct 524 ms 29676 KB Output is correct
7 Correct 548 ms 29860 KB Output is correct
8 Correct 533 ms 29804 KB Output is correct
9 Correct 400 ms 29804 KB Output is correct
10 Correct 400 ms 29676 KB Output is correct
11 Correct 411 ms 29676 KB Output is correct
12 Correct 485 ms 29804 KB Output is correct
13 Correct 528 ms 29752 KB Output is correct
14 Correct 538 ms 29712 KB Output is correct
15 Correct 538 ms 29804 KB Output is correct
16 Correct 538 ms 29804 KB Output is correct
17 Correct 564 ms 29932 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 9984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -