Submission #75956

#	Time	Username	Problem	Language	Result	Execution time	Memory
75956		mhnd	늑대인간 (IOI18_werewolf)	C++14	0 / 100	2822 ms	525312 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5+50;
const int oo = 1e9;
const int mod = 1e9+7;

vector<int> g[N];
int p[N],DFS,at,val,mn[4*N],mx[4*N],lf,ri,node[N],n;

void update(int n,int s ,int e){
	if(s > at || e < at)return;
	if(s == e){
		mn[n] = mx[n] = val;
		return;
	}
	update(n*2,s,(s+e)/2);
	update(n*2+1,(s+e)/2+1,e);
	mx[n] = max(mx[n*2+1],mx[n*2]);
	mn[n] = min(mn[n*2+1],mn[n*2]);
}

void dfs(int u,int p){
	node[u] = ++DFS;
	val = u;
	at = DFS;
	update(1,1,n);
	for(int i=0;i<g[u].size();i++){
		int v = g[u][i];
		if(v == p)continue;
		dfs(v,u);
	}
}

int getmn(int n,int s,int e){
	if(s > ri || e < lf)return 1e9;
	if(s >= lf && e <= ri)return mn[n];
	return min(getmn(n*2,s,(s+e)/2),getmn(2*n+1,(s+e)/2+1,e));
}

int getmx(int n,int s,int e){
	if(s > ri || e < lf)return 0;
	if(s >= lf && e <= ri)return mx[n];
	return max(getmx(n*2,s,(s+e)/2),getmx(2*n+1,(s+e)/2+1,e));
}

vector<int> check_validity(int N, vector<int> U, vector<int> V,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
	n = N;
	int Q = S.size();
	vector<int> A(Q,0);
	for(int i=0;i<N-1;i++){
		g[U[i]].push_back(V[i]);
		g[V[i]].push_back(U[i]);
		p[U[i]]++;
		p[V[i]]++;
	}
	for(int i=0;i<N;i++){
		if(p[i] == 1){
			dfs(i,-1);
			break;
		}
	}
	for(int i=0;i<Q;i++){
		int l = L[i],r = R[i],s=S[i],e = E[i];
		s = node[s];
		e = node[e];
		if(s > e){
			swap(s,e);
			int md,lo = s,hi = e,at= s-1;
			while(lo <= hi){
				md = (lo+hi)/2;
				lf = s;
				ri = md;
				if(getmx(1,1,n) > r)hi = md-1;
				else{
					lo = md+1;
					at = md;
				}
			}
			lo = s;
			hi = e;
			int at2 = e+1;
			while(lo<=hi){
				md = (lo+hi)/2;
				lf = md;
				ri = e;
				if(getmn(1,1,n)< l)lo = md+1;
				else{
					hi = md-1;
					at2 = md;
				}
			}
			cout << at << ' ' << at2 << endl;
			if(at >= at2)A[i]=1;
		}else{
			int md,lo = s,hi = e,at = s-1;
			while(lo <= hi){
				md = (lo+hi)/2;
				lf = s;
				ri = md;
				if(getmn(1,1,n) < l){
					hi = md-1;
				}else{
					lo = md+1;
					at = md;
				}
			}
			lo = s;
			hi = e;
			int at2 = e+1;
			while(lo <= hi){
				md = (lo+hi)/2;
				lf = md;
				ri = e;
				if(getmx(1,1,n) > r){
					lo = md+1;
				}else{
					hi = md-1;
					at2 = md;
				}
			}
			cout << at << ' ' << at2 << endl;
			if(at >= at2)A[i] = 1;
		}
	}
	return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++){
              ~^~~~~~~~~~~~

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