Submission #500224

#	Time	Username	Problem	Language	Result	Execution time	Memory
500224		REALITYNB	Werewolf (IOI18_werewolf)	C++17	0 / 100	843 ms	524292 KiB

werewolf

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

#define pb push_back
using namespace std; 
const int N=2e5+1,lg=20,inf=1e9; 
vector<int> adj[N]; 
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 M=X.size(); 
	for(int i=0;i<M;i++){
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);  
	}
	vector<vector<int>> sp(lg,vector<int>(N,-1)),mn(lg,vector<int>(N,inf)),mx(lg,vector<int>(N,-inf));  
	vector<int> lvl(N),in(N),out(N);  
	int time=0; 
	function<void(int,int,int)> dfs=[&](int a , int p ,int l){
		sp[0][a]=p,mn[0][a]=mx[0][a]=a; 
		if(p!=-1) 
			mn[0][a]=min(mn[0][a],p); 
		if(p!=-1)
			mx[0][a]=max(mx[0][a],p); 
		in[a]=++time,lvl[a]=l; 
		for(int i=1;i<lg;i++)
			if(sp[i-1][a]!=-1)
				sp[i][a]=sp[i-1][sp[i-1][a]],mn[i][a]=min(mn[i-1][a],mn[i-1][sp[i-1][a]]),mx[i][a]=max(mx[i-1][a],mx[i-1][sp[i-1][a]]); 
		for(int x : adj[a])
			if(x!=p) 
				dfs(x,a,l+1); 
		out[a]=++time; 
		return ; 
	}; 
	function<bool(int,int)> is_ancestor=[&](int p ,int a){
		return (in[p]<=in[a]&&out[a]<=out[p]); 
	}; 
	function<int(int,int)> lca=[&](int a, int b){
		if(is_ancestor(a,b)) return a; 
		if(is_ancestor(b,a)) return b; 
		for(int i=lg-1;i>-1;i--)
			if(sp[i][a]!=-1&&!is_ancestor(sp[i][a],b)) 
				a=sp[i][a]; 
		return sp[0][a]; 
	}; 
	function<int(int,int)> query=[&](int a , int lvl){
		int answer=inf ; 
		for(int i=0;i<lg;i++) 
			if((1<<i)&lvl){
				answer=min(answer,mn[i][a]); 
				a=sp[i][a]; 
			}
		return answer; 
	}; 
	function<int(int,int)> querymx=[&](int a , int lvl){
		int answer=-inf ; 
		for(int i=0;i<lg;i++) 
			if((1<<i)&lvl){
				answer=max(answer,mn[i][a]); 
				a=sp[i][a]; 
			}
		return answer; 
	}; 

	dfs(1,-1,0); 
	vector<int> result ; 
	for(int i=0;i<E.size();i++){
		int s=S[i],e=E[i],l=L[i],r=R[i]; 
		int lc=lca(s,e); 
		if(query(s,lvl[s]-lvl[lc])<l){
			int fs=s; 
			for(int i=lg-1;i>-1;i--)
				if(sp[i][fs]!=-1&&is_ancestor(lc,sp[i][fs])&&mn[i][fs]>=l)
					fs=sp[i][fs]; 
			int other= querymx(e,lvl[e]-lvl[lc]); 
			if(fs!=lc)
				other=max(other,querymx(sp[0][fs],lvl[sp[0][fs]]-lvl[lc])); 
			if(l<=fs&&fs<=r&&other<=r)
				result.pb(1); 
			else{
				int fe=e; 
				for(int i=lg-1;i>-1;--i)
					if(sp[i][fe]!=-1&&is_ancestor(lc,sp[i][fe])&&mx[i][fe]<=r)
						fe=sp[i][fe]; 
				int other=query(s,lvl[s]-lvl[lc]); 
				if(fe!=lc)
					other=min(other,query(sp[0][fe],lvl[sp[0][fe]]-lvl[lc])); 
				if(l<=fe&&fe<=r&&other>=l)
					result.pb(1);
				else
					result.pb(0); 
			}
		}
	}
	return result; 
}

Compilation message (stderr)

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:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<E.size();i++){
      |              ~^~~~~~~~~

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