oj.uz

Submission #312730

# Submission time Handle Problem Language Result Execution time Memory
312730 2020-10-14T09:02:49 Z reymontada61 Werewolf (IOI18_werewolf) C++14
34 / 100
 2596 ms 524292 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 432 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 432 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1921 ms 65396 KB Output is correct
2 Correct 2596 ms 73068 KB Output is correct
3 Correct 2585 ms 73196 KB Output is correct
4 Correct 2461 ms 72880 KB Output is correct
5 Correct 2393 ms 72940 KB Output is correct
6 Correct 2102 ms 73068 KB Output is correct
7 Correct 2122 ms 73196 KB Output is correct
8 Correct 2116 ms 73196 KB Output is correct
9 Correct 1100 ms 73068 KB Output is correct
10 Correct 990 ms 73200 KB Output is correct
11 Correct 1148 ms 73196 KB Output is correct
12 Correct 922 ms 73068 KB Output is correct
13 Correct 2531 ms 73068 KB Output is correct
14 Correct 2567 ms 73192 KB Output is correct
15 Correct 2517 ms 73136 KB Output is correct
16 Correct 2514 ms 73200 KB Output is correct
17 Correct 2116 ms 73072 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 432 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -