Submission #118839

#	Time	Username	Problem	Language	Result	Execution time	Memory
118839		Mamnoon_Siam	Werewolf (IOI18_werewolf)	C++17	15 / 100	4101 ms	77588 KiB

werewolf

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

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using VI = vector<int>;
const int maxn = 4e5 + 5;

int N, M, Q;
int U[maxn], V[maxn];
namespace pre {
	int parent[maxn];
	vector<int> g[maxn], w[maxn];
	int sz[maxn], par[maxn], pw[maxn];
	int in[maxn], tour[maxn];
	int tym = 0;
	void init() {
		for(int i = 0; i < N; i++) {
			sz[i] = 1, par[i] = i;
		}
	}
	int find(int u) {
		return par[u] == u ? u : find(par[u]);
	}
	void join(int u, int v) {
		int weight = max(u, v);
		u = find(u), v = find(v);
		if(u == v) return;
		if(sz[u] > sz[v]) swap(u, v);
		par[u] = v, pw[u] = weight;
		sz[v] += sz[u];
		g[v].emplace_back(u);
		w[v].emplace_back(weight);
	}
	void dfs(int u) {
		tour[tym] = u;
		in[u] = tym++;
		for(int v : g[u]) {
			dfs(v);
		}
	}
	pair<int, int> range(int u, int weight) {
		while(par[u] != u and pw[u] <= weight)
			u = par[u];
		if(sz[u] == 1) // leaf
			return {in[u], in[u]};
		int it = upper_bound(all(w[u]), weight) - w[u].begin();
		if(it == 0) // can't go nowhere
			return {in[u], in[u]};
		int v = g[u][it - 1];
		return {in[u], in[v] + sz[v] - 1};
	}
	vector<int> reachable_nodes(int u, int weight) {
		int l, r;
		tie(l, r) = range(u, weight);
		return vector<int>(tour + l, tour + r + 1);
	}
}
namespace suf {
	int parent[maxn];
	vector<int> g[maxn], w[maxn];
	int sz[maxn], par[maxn], pw[maxn];
	int in[maxn], tour[maxn];
	int tym = 0;
	void init() {
		for(int i = 0; i < N; i++) {
			sz[i] = 1, par[i] = i;
		}
	}
	int find(int u) {
		return par[u] == u ? u : find(par[u]);
	}
	void join(int u, int v) {
		int weight = min(u, v);
		u = find(u), v = find(v);
		if(u == v) return;
		if(sz[u] > sz[v]) swap(u, v);
		par[u] = v, pw[u] = weight;
		sz[v] += sz[u];
		g[v].emplace_back(u);
		w[v].emplace_back(weight);
	}
	void dfs(int u) {
		tour[tym] = u;
		in[u] = tym++;
		for(int v : g[u]) {
			dfs(v);
		}
	}
	pair<int, int> range(int u, int weight) {
		while(par[u] != u and pw[u] >= weight)
			u = par[u];
		if(sz[u] == 1) // leaf
			return {in[u], in[u]};
		int it = upper_bound(all(w[u]), weight, [](int x, int y){ return x > y; }) - w[u].begin();
		if(it == 0) // can't go nowhere
			return {in[u], in[u]};
		int v = g[u][it - 1];
		return {in[u], in[v] + sz[v] - 1};
	}
	vector<int> reachable_nodes(int u, int weight) {
		int l, r;
		tie(l, r) = range(u, weight);
		return vector<int>(tour + l, tour + r + 1);
	}
}

vector<int> check_validity(int _N, VI X, VI Y, VI S, VI E, VI L, VI R) {
	N = _N, M = X.size(), Q = S.size();
	for(int i = 0; i < M; i++) {
		U[i] = X[i], V[i] = Y[i];
		if(U[i] > V[i]) swap(U[i], V[i]);
	}

	pre::init();
	suf::init();

	vector<int> p(M), q(M);
	iota(p.begin(), p.end(), 0);
	iota(q.begin(), q.end(), 0);
	sort(p.begin(), p.end(), [](int x, int y){ return V[x] < V[y]; });
	sort(q.begin(), q.end(), [](int x, int y){ return U[x] > U[y]; });

	for(int i : p)
		pre::join(U[i], V[i]);
	for(int i : q)
		suf::join(U[i], V[i]);

	pre::dfs(pre::find(0));
	suf::dfs(suf::find(0));

	vector<int> ans;
	for(int i = 0; i < Q; i++) {
		vector<int> leq = pre::reachable_nodes(E[i], R[i]);
		vector<int> geq = suf::reachable_nodes(S[i], L[i]);
		sort(all(leq));
		sort(all(geq));
		vector<int> intersection;
		auto it = set_intersection(all(leq), all(geq), back_inserter(intersection));
		ans.emplace_back(bool(intersection.size()));
	}
	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, VI, VI, VI, VI, VI, VI)':
werewolf.cpp:140:8: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   auto it = set_intersection(all(leq), all(geq), back_inserter(intersection));
        ^~

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