Submission #792670

#	Time	Username	Problem	Language	Result	Execution time	Memory
792670		Sohsoh84	Werewolf (IOI18_werewolf)	C++17	100 / 100	1004 ms	243476 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pll;

#define all(x)		(x).begin(), (x).end()
#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;
const int LOG = 20;

int n, m, q;

namespace DSU_L {
	int C[MAXN], F[MAXN], par[MAXN][LOG], sz, T[MAXN], dfs_time, tin[MAXN], tout[MAXN];
	vector<int> adj[MAXN];

	inline void init() {
		sz = n - 1;
		T[0] = -1;
		for (int i = 0; i < n; i++) {
			F[i] = C[i] = i;
			T[i] = MAXN;
		}
	}

	inline int find(int v) {
		return C[v] == v ? v : C[v] = find(C[v]);
	}

	inline bool unite(int u, int v, int l) {
		u = find(u), v = find(v);
		if (u == v) return false;

		int fu = F[u], fv = F[v];
		sz++;
		par[fu][0] = sz;
		par[fv][0] = sz;
		
		C[v] = u;
		T[sz] = l;
		F[u] = sz;
		
		adj[sz].push_back(fu);
		adj[sz].push_back(fv);

		return true;
	}

	void dfs(int v) {
		tin[v] = ++dfs_time;
		for (int u : adj[v])
			dfs(u);
		
		tout[v] = dfs_time;
	}

	inline void init_tree() {
		dfs(sz);
		par[sz][0] = sz;
		for (int i = 1; i < LOG; i++)
			for (int v = 0; v <= sz; v++)
				par[v][i] = par[par[v][i - 1]][i - 1];
	}

	inline int max_node(int v, int l) {
		for (int i = LOG - 1; i >= 0; i--)
			if (T[par[v][i]] >= l)
				v = par[v][i];

		return v;
	} 

	inline pll get_seg(int v, int l) {
		v = max_node(v, l);
		return {tin[v], tout[v]};
	}
}

namespace DSU_R {
	int par[MAXN];
	vector<int> C[MAXN];
	set<int> st[MAXN];

	inline void init() {
		for (int i = 0; i < n; i++) {
			st[i].insert(DSU_L::tin[i]);
			par[i] = i;
			C[i].push_back(i);
		}
	}

	inline bool unite(int u, int v) {
		u = par[u], v = par[v];
		if (u == v) return false;
		if (C[u].size() < C[v].size()) swap(u, v);

		for (int e : C[v]) {
			C[u].push_back(e);
			par[e] = u;
		}

		for (int e : st[v])
			st[u].insert(e);

		C[v].clear();
		st[v].clear();
		return true;
	}

	inline bool get(int v, int l, int r) {
		v = par[v];
		auto it = st[v].lower_bound(l);
		return it != st[v].end() && *it <= r;
	}
}

vector<int> ans, adj[MAXN], QR[MAXN];

vector<int> check_validity(int N_, vector<int> X_, vector<int> Y_,
	vector<int> S, vector<int> E,
	vector<int> L, vector<int> R) {
	
	n = N_;
	m = X_.size();
	q = S.size();
	
	for (int i = 0; i < m; i++) {
		adj[X_[i]].push_back(Y_[i]);
		adj[Y_[i]].push_back(X_[i]);
	}

	DSU_L::init();

	for (int v = n - 1; v >= 0; v--) {
		for (int u : adj[v]) {
			if (u < v) continue;
			DSU_L::unite(u, v, v);	
		}
	}
	
	DSU_L::init_tree();
	DSU_R::init();
	
	for (int i = 0; i < q; i++)
		QR[R[i]].push_back(i);

	ans.resize(q);
	for (int r = 0; r < n; r++) {
		for (int u : adj[r]) {
			if (u > r) continue;
			DSU_R::unite(r, u);
		}

		for (int i : QR[r]) {
			auto [tl, tr] = DSU_L::get_seg(S[i], L[i]);
			ans[i] = DSU_R::get(E[i], tl, tr);
		}
	}

	return ans;
}

// TODO: fill ans

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