Submission #990172

#	Time	Username	Problem	Language	Result	Execution time	Memory
990172		vqpahmad	Werewolf (IOI18_werewolf)	C++17	100 / 100	764 ms	305336 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct MergeTree {
	int p[MAXN], s[MAXN], lebal[MAXN];
	int cur_node;
	vector<int> adj[MAXN];
	void init(int n){
		cur_node = n;
		for (int i = 0; i < n; i++){
			p[i] = i;
			s[i] = 1;
			lebal[i] = i;
		}
	}
	int find(int u){
		if (p[u] == u) return u;
		return p[u] = find(p[u]);
	}
	void merge(int u, int v){
		u = find(u);
		v = find(v);
		if (u == v) return;
		adj[cur_node].pb(lebal[u]);
		adj[cur_node].pb(lebal[v]);
		adj[lebal[u]].pb(cur_node);
		adj[lebal[v]].pb(cur_node);

		if (s[u] < s[v]) swap(u, v);
		s[u] += s[v];
		p[v] = u;
		lebal[u] = cur_node++;
	}
	int st[MAXN], ft[MAXN], timer = 1;
	int mn[MAXN], mx[MAXN]; // for humans I need min, for werewolf max
	int fa[MAXN][20];
	void dfs(int node, int par){
		st[node] = timer++;
		fa[node][0] = par;
		for (int b = 1; b < 20; b++){
			fa[node][b] = fa[fa[node][b - 1]][b - 1];
		}
		if (sz(adj[node]) == 1 && adj[node][0] == par){
			mx[node] = node;
			mn[node] = node;
		}
		for (auto to : adj[node]){
			if (to != par){
				dfs(to, node);
				ckmax(mx[node], mx[to]);
				ckmin(mn[node], mn[to]);
			}
		}
		ft[node] = timer++;
	}
	void get_dfs_order(){
		cur_node--;
		for (int i = 0; i <= cur_node; i++){
			mn[i] = inf;
			mx[i] = -inf;
		}
		dfs(cur_node, cur_node);
	}
	pii find_range(int u, int time, bool human){
		for (int b = 19; b >= 0; b--){
			if (human && mn[fa[u][b]] >= time){
				u = fa[u][b];
			}
			if (!human && mx[fa[u][b]] <= time){
				u = fa[u][b];
			}
		}
		return {st[u], ft[u]};
	}
	void dbg(){
		cout << "HERE\n";
		for (int i = 0; i <= cur_node; i++){
			cout << i << ' ' << st[i] << ' ' << ft[i] << ' ' << mn[i] << ' ' << mx[i] << endl;
		}
	}
} human, werewolf;

const int off = (1<<20);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
	int t[off<<1];
	void update(int idx, int u){
		t[idx+=off] += u;
		while (idx/=2)
			t[idx] = t[ls] + t[rs];
	}
	int get(int l, int r, int idx=1, int lo=0, int hi=off){
		if (r <= lo || hi <= l) 
			return 0;
		if (l <= lo && hi <= r)
			return t[idx];
		int mi = (lo+hi)>>1;
		return get(l, r, ls, lo, mi)+get(l, r, rs, mi, hi);
	}
} seg;

vector<int> adj[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) {
	int m = sz(X);
	int Q = S.size();
	for (int i = 0; i < m; i++){
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	werewolf.init(n);
	for (int i = 0; i < n; i++){
		// I want to caclute component for werewolf for L <= i
		for (auto u : adj[i]){
			if (u <= i){
				werewolf.merge(i, u);
			}
		}
	}
	human.init(n);
	for (int i = n - 1; i >= 0; i--){
		// I want to caclute component for werewolf for L <= i
		for (auto u : adj[i]){
			if (u >= i){
				human.merge(i, u);
			}
		}
	}
	werewolf.get_dfs_order();
	human.get_dfs_order();
	//werewolf.dbg();
	//human.dbg();
	vector<int> add[MAXN];
	for (int i = 0; i < n; i++){
		add[human.st[i]].pb(werewolf.st[i]);
	}
	vector<array<int, 4>> Queries[MAXN]; // type, bot, top, idx
	for (int i = 0; i < Q; i++){
		pii hr = human.find_range(S[i], L[i], 1);
		pii wr = werewolf.find_range(E[i], R[i], 0);
		Queries[hr.F - 1].pb({-1, wr.F, wr.S, i});
		Queries[hr.S].pb({1, wr.F, wr.S, i});
	}
	vector<int> ans(Q);
	for (int i = 0; i < MAXN; i++){
		for (auto pos : add[i]){
			seg.update(pos, 1);
		}
		for (auto [type, bot, top, idx] : Queries[i]){
			ans[idx] += type * seg.get(bot, top);
		}
	}
	for (int i = 0; i < Q; ++i) {
		ans[i] = !!ans[i];
	}
	return ans;
}

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