Submission #295881

#	Time	Username	Problem	Language	Result	Execution time	Memory
295881		SeDunion	Werewolf (IOI18_werewolf)	C++17	34 / 100	3112 ms	524292 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5;
vector<int>vec,g[MAXN];
int pos[MAXN];
int mn[MAXN << 2], mx[MAXN << 2];
void dfs (int v, int p = -1) {
	vec.push_back (v);
	for (int to : g[v]) if (to != p) dfs (to, v);
}
void build (int l = 0, int r = vec.size(), int v = 0) {
	if (r - l == 1) { mn[v] = mx[v] = vec[l]; return; }
	int m = (l + r) >> 1;
	build (l, m, v + v + 1), build (m, r, v + v + 2);
	mn[v] = min (mn[v + v + 1], mn[v + v + 2]);
	mx[v] = max (mx[v + v + 1], mx[v + v + 2]);
}
int getmn (int L, int R, int l = 0, int r = vec.size(), int v = 0) {
	if (L <= l && r <= R) return mn[v];
	if (L >= r || l >= R) return MAXN;
	int m = (l + r) >> 1;
	return min (getmn (L, R, l, m, v + v + 1), getmn (L, R, m, r, v + v + 2));
}
int getmx (int L, int R, int l = 0, int r = vec.size(), int v = 0) {
	if (L <= l && r <= R) return mx[v];
	if (L >= r || l >= R) return -MAXN;
	int m = (l + r) >> 1;
	return max (getmx (L, R, l, m, v + v + 1), getmx (L, R, m, r, v + v + 2));
}
vector<int> check_validity
(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int M = X.size();
	for (int i = 0 ; i < M ; ++ i) {
		g[X[i]].push_back (Y[i]);
		g[Y[i]].push_back (X[i]);
	}
	int root;
	for (int i = 0 ; i < N ; ++ i) {
		if (g[i].size() == 1) root = i;
	}
	dfs(root);
	assert (vec.size() == N);
	build();
	for (int i = 0 ; i < N ; ++ i) {
		pos[vec[i]] = i;
	}
	int Q = S.size();
	vector<int>ans(Q);
	for (int i = 0 ; i < Q ; ++ i) {
		int s = S[i], e = E[i];
		int l = pos[s], r = pos[e], res = 0;
		if (l <= r) {
			while (l <= r) {
				int m = (l + r) >> 1;
				bool lf = (getmn (pos[s], m + 1) >= L[i]);
				bool rg = (getmx (m, pos[e] + 1) <= R[i]);
				if (lf && rg) {
					res = 1;
					break;
				}
				if (!lf) r = m - 1;
				else l = m + 1;
			}
		} else {
			swap (l, r);
			swap (s, e);
			while (l <= r) {
				int m = (l + r) >> 1;
				bool lf = (getmx (pos[s], m + 1) <= R[i]);
				bool rg = (getmn (m, pos[e] + 1) >= L[i]);
				if (lf && rg) {
					res = 1;
					break;
				}
				if (!lf) r = m - 1;
				else l = m + 1;
			}
		}
		ans[i] = res;
	}
	return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from werewolf.cpp:2:
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:43:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |  assert (vec.size() == N);
      |          ~~~~~~~~~~~^~~~
werewolf.cpp:42:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |  dfs(root);
      |  ~~~^~~~~~

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