Submission #312730

#	Time	Username	Problem	Language	Result	Execution time	Memory
312730		reymontada61	Werewolf (IOI18_werewolf)	C++14	34 / 100	2596 ms	524292 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

int n;
const int MXN = 200005, MXK = 20;
vector<int> adj[MXN];

vector<int> ord;

void dfs(int node, int par = -1) {
	ord.push_back(node);
	for (auto x: adj[node]) {
		if (x == par) continue;
		dfs(x, node);
	}
}

int stmax[MXN][MXK];
int stmin[MXN][MXK];
int pos[MXN];

int qmax(int l, int r) {
	int k = (r - l + 1);
	int t = 0;
	while ((1 << (t + 1)) <= k) t++;
	return max(stmax[l][t], stmax[r-(1<<t)+1][t]);
}

int qmin(int l, int r) {
	int k = (r - l + 1);
	int t = 0;
	while ((1 << (t + 1)) <= k) t++;
	return min(stmin[l][t], stmin[r-(1<<t)+1][t]);
}

pair<int, int> around(int center, int minokay, int maxokay) {
	int low = 0;
	int high = center + 1;
	while (low + 1 < high) {
		int mid = (low + high) / 2;
		if ((qmin(mid, center) < minokay) || (qmax(mid, center) > maxokay))  {
			low = mid;
		}
		else {
			high = mid;
		}
	}
	int L = low;
	if ((qmin(low, center) < minokay) || (qmax(low, center) > maxokay)) L++;
	
	low = center;
	high = n;
	
	while (low + 1 < high) {
		int mid = (low + high) / 2;
		if ((qmin(center, mid) < minokay) || (qmax(center, mid) > maxokay))  {
			high = mid;
		}
		else {
			low = mid;
		}
	}
	
	int R = low;
	if ((qmin(center, low) < minokay) || (qmax(center, low) > maxokay)) R--;
	return {L, R};
}

bool itr(pair<int, int> a, pair<int, int> b) {
	if (a > b) swap(a, b);
	return (b.first >= a.first && b.first <= a.second);
}

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) {
	int Q = S.size();
	vector<int> A;
	
	n = N;
	int M = X.size();
  
	for (int i=0; i<M; i++) {
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	
	int starter = -1;
	for (int i=0; i<N; i++) {
		if (adj[i].size() == 1) starter = i;
	}
	
	dfs(starter);
	
	for (int i=0; i<MXN; i++) {
		for (int j=0; j<MXK; j++) {
			stmax[i][j] = INT_MAX;
			stmin[i][j] = INT_MIN;
		}
	}
	
	for (int i=0; i<N; i++) {
		pos[ord[i]] = i;
		stmax[i][0] = ord[i];
		stmin[i][0] = ord[i];
	}
	
	for (int j=1; j<MXK; j++) {
		int L = 1 << (j - 1);
		for (int i=0; i<N; i++) {
			if (i + L < N) {
				stmax[i][j] = max(stmax[i][j-1], stmax[i+L][j-1]);
				stmin[i][j] = min(stmin[i][j-1], stmin[i+L][j-1]);
			}
		}
	}
	
	for (int i=0; i<Q; i++) {
		
		int s = S[i], e = E[i], l = L[i], r = R[i];
		
		int spos = pos[s];
		int epos = pos[e];
		
		if (ord[spos] < l || ord[epos] > r) {
			A.push_back(0);
			continue;
		}
		
		pair<int, int> srange = around(spos, l, N-1);
		pair<int, int> erange = around(epos, 0, r);
		
		A.push_back(itr(srange, erange));
		
	}
  
	return A;
	
	
}

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