oj.uz

Submission #312791

# Submission time Handle Problem Language Result Execution time Memory
312791 2020-10-14T11:27:32 Z reymontada61 Werewolf (IOI18_werewolf) C++14
34 / 100
 1678 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 = 31 - __builtin_clz(k);
	return max(stmax[l][t], stmax[r-(1<<t)+1][t]);
}

int qmin(int l, int r) {
	int k = (r - l + 1);
	int t = 31 - __builtin_clz(k);
	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 428 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 428 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 1556 ms 67752 KB Output is correct
2 Correct 1665 ms 70252 KB Output is correct
3 Correct 1660 ms 70124 KB Output is correct
4 Correct 1584 ms 70380 KB Output is correct
5 Correct 1585 ms 70432 KB Output is correct
6 Correct 1517 ms 70124 KB Output is correct
7 Correct 1611 ms 70180 KB Output is correct
8 Correct 1473 ms 70096 KB Output is correct
9 Correct 839 ms 70184 KB Output is correct
10 Correct 773 ms 70124 KB Output is correct
11 Correct 874 ms 70128 KB Output is correct
12 Correct 691 ms 70124 KB Output is correct
13 Correct 1653 ms 70252 KB Output is correct
14 Correct 1665 ms 70252 KB Output is correct
15 Correct 1657 ms 70404 KB Output is correct
16 Correct 1678 ms 70300 KB Output is correct
17 Correct 1535 ms 70224 KB Output is correct

Subtask #4
0 / 51.0

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