Submission #138188

#	Time	Username	Problem	Language	Result	Execution time	Memory
138188		wzy	Werewolf (IOI18_werewolf)	C++11	34 / 100	2480 ms	44744 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
bool vis[N];
int Lx , Rx;
vector<int> adj[N];
vector<int> v;
int nx ; 
int pos[N];
void solve(int x ){
	v.push_back(x);
	vis[x] = true;
	for(auto w : adj[x]){
		if(!vis[w]){
			solve(w);
		}
	}
}

struct node{
	int minvl , maxvl;
} st[4*N];

node merge(node a , node b){
	node x;
	x.minvl = min(a.minvl , b.minvl);
	x.maxvl = max(a.maxvl , b.maxvl);
	return x;
}

void build(int l = 0 , int r = nx - 1 , int curr = 1){
	// cout<<l<<" " <<r <<" " << curr << endl;
	int mid =  (l+r)/2;
	if(l == r){
		st[curr].minvl = st[curr].maxvl = v[l];
		return ;
	}
	build(l , mid , 2*curr);
	build(mid + 1 , r , 2*curr + 1);
	st[curr] = merge(st[2*curr] , st[2*curr + 1]);
}

node query(int x , int y , int  l = 0 , int r = nx -1 , int curr = 1){
	int mid = (l+r)/2;
	if(l == x && r == y){
		return st[curr];
	}
	if(y <= mid){
		return query(x,y,l,mid,2*curr);
	}
	else if(x > mid){
		return query(x,y,mid+1 , r , 2*curr +1);
	}
	else{
		return merge(query(x,mid,l,mid,2*curr) , query(mid + 1 , y , mid + 1 , r , 2*curr + 1));
	}
}



std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E,  std::vector<int> L, std::vector<int> R) {
  nx = N ;
  for(int i = 0 ; i < X.size() ; i ++){
  	adj[X[i]].push_back(Y[i]);
  	adj[Y[i]].push_back(X[i]);
  }  
  for(int i = 0 ; i < N ; i ++){
  	if(adj[i].size() == 1){
  		solve(i);
  		break;
  	}
  }
  for(int i = 0 ; i < N ; i ++){
  	pos[v[i]] = i;
  }
  build();
  int Q = S.size();
  std::vector<int> A(Q, 0);
  for(int i = 0; i < Q; ++i) {
    if(pos[S[i]] < pos[E[i]]){
    	int l = pos[S[i]] , r = pos[E[i]];
    	int ansj = l;
    	while(l<=r){
    		int mid = (l+r)/2;
    		if(query(pos[S[i]] , mid).minvl < L[i]){
    			r = mid - 1;
    		}
    		else{
    			l = mid + 1;
    			ansj = mid;
    		}
    	}
    	l = pos[S[i]] , r = pos[E[i]];
    	int ansj2 = r;
    	while(l<=r){
    		int mid = (l+r)/2;
    		if(query(mid , pos[E[i]]).maxvl > R[i]){
    			l = mid + 1;
    		}
    		else{
    			r = mid - 1;
    			ansj2 = mid;
    		}
    	}
    	if(ansj >= ansj2){
    		A[i] = 1;
    	}
    }
    else{
    	int l = pos[E[i]] , r = pos[S[i]];
    	int ansj = l;
    	while(l<=r){
    		int mid = (l+r)/2;
    		if(query(pos[E[i]] , mid).maxvl > R[i]){
    			r = mid - 1;
    		}
    		else{
    			l = mid + 1;
    			ansj = mid;
    		}
    	}
    	l = pos[E[i]] , r = pos[S[i]];
    	int ansj2 = r;
    	while(l<=r){
    		int mid = (l+r)/2;
    		if(query(mid , pos[S[i]]).minvl < L[i]){
    			l = mid + 1;
    		}
    		else{
    			r = mid - 1;
    			ansj2 = mid;
    		}
    	}
    	if(ansj >= ansj2){
    		A[i] = 1;
    	}    	
    }
  }
  return A;
}

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:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < X.size() ; i ++){
                   ~~^~~~~~~~~~

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