Submission #1184645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184645		Nonoze	Werewolf (IOI18_werewolf)	C++20	100 / 100	917 ms	240536 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()


struct dsu {
	int n;
	vector<int> par, val, l, r, p;
	vector<vector<int>> adj, up;
	dsu(int _n) : par(_n), adj(_n), n(_n), val(_n), l(_n), r(_n), p(_n) {
		iota(all(par), 0), iota(all(val), 0);
	}
	int get(int x) {
		if (x==par[x]) return x;
		return par[x] = get(par[x]);
	}

	void unite(int x, int y, int basex) {
		x=get(x), y=get(y);
		if (x==y) return;
		adj.pb({x, y}), par.pb(n), val.pb(basex), l.pb(0), r.pb(0), p.pb(n);
		par[x]=par[y]=p[x]=p[y]=n;
		n++;
	}

	vector<int> become;
	int act=0;

	void dfs(int u) {
		l[u]=act;
		for (int v: adj[u]) dfs(v);
		if (u<sz(become)) become[u]=act++;
		r[u]=act-1;
	}

	vector<int> plane(int m) {
		become.resize(m);
		for (int i=0; i<n; i++) if (par[i]==i) dfs(i);
		return become;
	}

	void calcup() {
		up.resize(n, vector<int>(20, -1));
		for (int i=n-1; i>=0; i--) {
			up[i][0]=p[i];
			for (int j=1; j<20; j++) up[i][j]=up[up[i][j-1]][j-1];
		}
	}
} wolf(0), human(0);


int n, m, q;
vector<int> ans;
vector<vector<pair<int, int>>> queries;

set<int> dfs(int u) {
	set<int> st;
	if (u<n) st.insert(u);
	for (int v: wolf.adj[u]) {
		if (v==wolf.par[u]) continue;
		set<int> st2=dfs(v);
		if (st2.size()>st.size()) swap(st, st2);
		for (int x: st2) {
			if (st.count(x)) st.erase(x);
			else st.insert(x);
		}
	}

	for (auto [x, i]: queries[u]) {
		int l=human.l[x], r=human.r[x];
		auto lb=st.lower_bound(l);
		if (lb!=st.end() && *lb<=r) ans[i]=1;
		else ans[i]=0;
	}
	
	return move(st);
}


vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	q = sz(S), m=sz(X), n=N;
	vector<vector<int>> adj(n);
	for (int i=0; i<m; i++) adj[X[i]].pb(Y[i]), adj[Y[i]].pb(X[i]);
	human=dsu(n);
	for (int i=n-1; i>=0; i--) for (int j: adj[i]) if (j>i) human.unite(i, j, i);
	vector<int> become=human.plane(n);
	wolf=dsu(n);
	for (int i=0; i<n; i++) for (int j: adj[i]) if (j<i) wolf.unite(become[i], become[j], i);
	human.calcup(), wolf.calcup();
	ans.resize(q), queries.resize(wolf.n);
	for (int i=0; i<q; i++) {
		int x=S[i], y=become[E[i]], l=L[i], r=R[i];
		for (int j=19; j>=0; j--) if (human.val[human.up[x][j]]>=l) x=human.up[x][j];
		for (int j=19; j>=0; j--) if (wolf.val[wolf.up[y][j]]<=r) y=wolf.up[y][j];
		queries[y].pb({x, i});
	}
	for (int i=0; i<wolf.n; i++) {
		if (wolf.par[i]==i) dfs(i);
	}
	return ans;
}

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