Submission #139196

#	Time	Username	Problem	Language	Result	Execution time	Memory
139196		rajarshi_basu	Werewolf (IOI18_werewolf)	C++14	0 / 100	419 ms	367096 KiB

werewolf

#include <bits/stdc++.h>

#include "werewolf.h"

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define vv vector
#define ii pair<int,int>

using namespace std;

const int MAXN = 2*100*1000 +1;
const int INF = 2*MAXN;
vi g[MAXN];
int n;

struct SegmentTree{
	int st[4*MAXN];
	void build(int node,int ss,int se,int* arr){
		FOR(i,n)st[i] = arr[i];return;
		
		
		if(ss == se){
			st[node] = arr[ss];
			return;
		}
		int mid = (ss+se)/2;
		build(node*2+1,ss,mid,arr);
		build(node*2+2,mid+1,se,arr);
		st[node] = min(st[node*2+1],st[node*2+2]);
	}
	int getLastValue(int node,int ss,int se,int bound,int val){
		/*se = bound;
		//se = min(se,bound);
		while(1){
			if(se == -1)break;
			if(st[se] < val)return se;
			se--;
		}
		return -1;*/
		
		
		if(ss > bound)return -1; 
		if(st[node] >= val)return -1;
		int mid = (ss+se)/2;
		if(ss == se)return ss;
		int vv = getLastValue(node*2+2,mid+1,se,bound,val);
		if(vv == -1)return getLastValue(node*2+1,ss,mid,bound,val);
		return vv;
	}
	int getFirstValue(int node,int ss,int se,int bound,int val){
		ss = bound;
		//ss = max(ss,bound);
		while(1){
			if(ss == n)break;
			if(st[ss] < val)return ss;
			ss++;
		}
		return n;
		
		
		if(ss > bound)return -1; 
		if(st[node] >= val)return -1;
		int mid = (ss+se)/2;
		if(ss == se)return ss;
		int vv = getLastValue(node*2+2,mid+1,se,bound,val);
		if(vv == -1)return getLastValue(node*2+1,ss,mid,bound,val);
		return vv;
	}
};

SegmentTree human_normal,human_reverse,wolf_normal,wolf_reverse;


int place[MAXN];
int rplace[MAXN];

int T = 0;
void dfs(int node,int p = -1){
	place[node] = T;
	rplace[T] = node;
	T++;
	for(auto e : g[node]){
		if(e != p)dfs(e,node);
	}
}

bool solve(int n,int l,int r,int s,int e){
	s = place[s];
	e = place[e];
	ii p1;
	ii p2;
	p1.ff = human_normal.getLastValue(0,0,n-1,s,l)  + 1;// + 1;
	p1.ss = human_normal.getFirstValue(0,0,n-1,s,l) - 1;// - 1;//n - human_reverse.getLastValue(0,0,n-1,n-s-1,l) - 1 -1;
	p2.ff = wolf_normal.getLastValue(0,0,n-1,e,-r)  + 1;// + 1;
	p2.ss = wolf_normal.getFirstValue(0,0,n-1,e,-r) - 1;// - 1;//n - wolf_reverse.getLastValue(0,0,n-1,n-e-1,-r) - 1 -1;	
	//while(1);
	
	if(p1.ff == p2.ff)return true;
	if(p1.ff > p2.ff)swap(p1,p2);
	return p1.ss >= p2.ff; 
	
}

vi check_validity(int n,vi x,vi y,vi s,vi e,vi l,vi r){
	FOR(i,(int)x.size()){
		g[x[i]].pb(y[i]);
		g[y[i]].pb(x[i]);
	}
	::n = n;
	int q = s.size();
	vi ret;FOR(i,q)ret.pb(0);
	// preprocess stuff
	
	int root = 0;
	FOR(i,n)if(g[i].size() == 1)root = i;
	dfs(root);
	
	int arr[n];
	
	FOR(i,n)arr[i] = rplace[i];
	human_normal.build(0,0,n-1,arr);
	
	FOR(i,n)arr[i] = rplace[n-i-1];
	human_reverse.build(0,0,n-1,arr);
	
	FOR(i,n)arr[i] = -rplace[i];
	wolf_normal.build(0,0,n-1,arr);
	
	FOR(i,n)arr[i] = -rplace[n-i-1];
	wolf_reverse.build(0,0,n-1,arr);
	
	//////////////////////////////////
	FOR(i,q){
		ret[i] = solve(n,l[i],r[i],s[i],e[i]);
	}
	return ret;
}

int ma1in(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}

Compilation message (stderr)

werewolf.cpp: In member function 'void SegmentTree::build(int, int, int, int*)':
werewolf.cpp:5:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i,n) for(int i=0;i<n;i++)
                  ^
werewolf.cpp:25:3: note: in expansion of macro 'FOR'
   FOR(i,n)st[i] = arr[i];return;
   ^~~
werewolf.cpp:25:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   FOR(i,n)st[i] = arr[i];return;
                          ^~~~~~

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