Submission #102700

#	Time	Username	Problem	Language	Result	Execution time	Memory
102700		bert30702	Werewolf (IOI18_werewolf)	C++17	100 / 100	2834 ms	165872 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int MX = 2e5 + 100;
vector<int> G[MX], G_mx[MX], G_mn[MX];
int boss_mx[MX], boss_mn[MX];
int l_mx[MX], r_mx[MX], l_mn[MX], r_mn[MX], tmp[MX];
vector<int> ptr_mn[MX], ptr_mx[MX];
vector<int> T[MX * 4];
void build_ptr_mn(int u, int p, int &ptr) {
	l_mn[u] = ++ptr;
	tmp[ptr] = u;
	if(p != -1) {
		ptr_mn[u].push_back(p);
		while(ptr_mn[ptr_mn[u].back()].size() >= ptr_mn[u].size()) {
			ptr_mn[u].push_back(ptr_mn[ptr_mn[u].back()][ptr_mn[u].size() - 1]);
		}
	}
	for(auto it: G_mn[u]) build_ptr_mn(it, u, ptr);
	r_mn[u] = ptr;
}
void build_ptr_mx(int u, int p, int &ptr) {
	l_mx[u] = ++ptr;
	if(p != -1) {
		ptr_mx[u].push_back(p);
		while(ptr_mx[ptr_mx[u].back()].size() >= ptr_mx[u].size()) {
			ptr_mx[u].push_back(ptr_mx[ptr_mx[u].back()][ptr_mx[u].size() - 1]);
		}
	}
	for(auto it: G_mx[u]) build_ptr_mx(it, u, ptr);
	r_mx[u] = ptr;
}
void build_T(int u, int l, int r) {
	if(l == r) return T[u] = {l_mx[tmp[l]]}, void();
	int m = l + r >> 1;
	build_T(u * 2 + 1,     l, m);
	build_T(u * 2 + 2, m + 1, r);
	T[u].resize(r - l + 1);
	merge(T[u * 2 + 1].begin(), T[u * 2 + 1].end(), T[u * 2 + 2].begin(), T[u * 2 + 2].end(), T[u].begin());
}
int query_T(int u, int l, int r, int s, int t, int a, int b) {
	if(l == s and r == t) return lower_bound(T[u].begin(), T[u].end(), a) != upper_bound(T[u].begin(), T[u].end(), b);
	int m = l + r >> 1;
	if(t <= m) return query_T(u * 2 + 1,     l, m, s, t, a, b);
	if(s >  m) return query_T(u * 2 + 2, m + 1, r, s, t, a, b);
	return query_T(u * 2 + 1, l, m, s, m, a, b) | query_T(u * 2 + 2, m + 1, r, m + 1, t, a, b);
}
vector<int> query(int N, vector<int> S, vector<int> T, vector<int> L, vector<int> R) {
	vector<int> ans;
	for(int i = 0; i < S.size(); i ++) {
		for(int j = 2000; j >= 0; j --) {
			if(ptr_mn[S[i]].empty()) break;
			j = min(j, (int) ptr_mn[S[i]].size() - 1);
			if(ptr_mn[S[i]][j] >= L[i]) S[i] = ptr_mn[S[i]][j];
		}
		for(int j = 2000; j >= 0; j --) {
			if(ptr_mx[T[i]].empty()) break;
			j = min(j, (int) ptr_mx[T[i]].size() - 1);
			if(ptr_mx[T[i]][j] <= R[i]) T[i] = ptr_mx[T[i]][j];
		}
		ans.push_back(query_T(0, 1, N, l_mn[S[i]], r_mn[S[i]], l_mx[T[i]], r_mx[T[i]]));
	}
	return ans;
}
int Find_mx(int u) {
	return boss_mx[u] == u ? u : boss_mx[u] = Find_mx(boss_mx[u]);
}
int Find_mn(int u) {
	return boss_mn[u] == u ? u : boss_mn[u] = Find_mn(boss_mn[u]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> T, vector<int> L, vector<int> R) {
	for(int i = 0; i < N; i ++) boss_mx[i] = boss_mn[i] = i;
	for(int i = 0; i < X.size(); i ++) {
		G[X[i]].push_back(Y[i]);
		G[Y[i]].push_back(X[i]);
	}
	for(int i = N - 1; i >= 0; i --) {
		for(auto it: G[i]) {
			if(it > i and Find_mn(it) != i) {
				G_mn[i].push_back(Find_mn(it));
				boss_mn[Find_mn(it)] = i;
			}
		}
	}
	for(int i = 0; i < N; i ++) {
		for(auto it: G[i]) {
			if(it < i and Find_mx(it) != i) {
				G_mx[i].push_back(Find_mx(it));
				boss_mx[Find_mx(it)] = i;
			}
		}
	}
	int ptr_mn = 0; build_ptr_mn(0    , -1, ptr_mn);
	int ptr_mx = 0; build_ptr_mx(N - 1, -1, ptr_mx);
	build_T(0, 1, N);
	return query(N, S, T, L, R);
}

Compilation message (stderr)

werewolf.cpp: In function 'void build_T(int, int, int)':
werewolf.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
werewolf.cpp: In function 'int query_T(int, int, int, int, int, int, int)':
werewolf.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
werewolf.cpp: In function 'std::vector<int> query(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i ++) {
                 ~~^~~~~~~~~~
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:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i ++) {
                 ~~^~~~~~~~~~

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