Submission #592880

#	Time	Username	Problem	Language	Result	Execution time	Memory
592880		Temmie	Werewolf (IOI18_werewolf)	C++17	100 / 100	1263 ms	120488 KiB

werewolf

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

struct Dsu {
	
	std::vector <int> p;
	std::vector <std::vector <int>> g;
	std::vector <int> tour;
	std::vector <int> l, r;
	
	inline Dsu(int s) {
		p.resize(s);
		std::iota(p.begin(), p.end(), 0);
		g.resize(s);
		l.resize(s);
		r.resize(s);
	}
	
	inline int find(int v) {
		return v == p[v] ? v : (p[v] = find(p[v]));
	}
	
	inline void unite(int u, int v) {
		if ((u = find(u)) != (v = find(v))) {
			g[u].push_back(v);
			p[v] = u;
		}
	}
	
	void make(int node) {
		l[node] = tour.size();
		tour.push_back(node);
		for (int x : g[node]) {
			make(x);
		}
		r[node] = tour.size();
	}
	
};

struct Rag {
	
	int size;
	std::vector <std::vector <int>> v;
	
	Rag(const std::vector <int>& a) {
		size = 1;
		while (size < (int) a.size()) {
			size <<= 1;
		}
		v.resize(size << 1);
		make(a, 0, 0, size = a.size());
	}
	
	void make(const std::vector <int>& a, int now, int l, int r) {
		if (!(r - l - 1)) {
			v[now].push_back(a[l]);
			return;
		}
		int mid = (l + r) >> 1;
		make(a, now * 2 + 1, l, mid);
		make(a, now * 2 + 2, mid, r);
		for (int lp = 0, rp = 0;
		lp < (int) v[now * 2 + 1].size() || rp < (int) v[now * 2 + 2].size(); ) {
			if (lp == (int) v[now * 2 + 1].size()) v[now].push_back(v[now * 2 + 2][rp++]);
			else if (rp == (int) v[now * 2 + 2].size()) v[now].push_back(v[now * 2 + 1][lp++]);
			else if (v[now * 2 + 1][lp] < v[now * 2 + 2][rp]) v[now].push_back(v[now * 2 + 1][lp++]);
			else v[now].push_back(v[now * 2 + 2][rp++]);
		}
	}
	
	int query(int tl, int tr, int le, int ri) {
		return query(tl, tr, le, ri, 0, 0, size);
	}
	
	int query(int tl, int tr, int le, int ri, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return 0;
		}
		if (l >= tl && r <= tr) {
			return
			std::lower_bound(v[now].begin(), v[now].end(), ri) -
			std::lower_bound(v[now].begin(), v[now].end(), le);
		}
		int mid = (l + r) >> 1;
		return query(tl, tr, le, ri, now * 2 + 1, l, mid) + query(tl, tr, le, ri, now * 2 + 2, mid, r);
	}
	
};

std::vector <int> check_validity(int n, std::vector <int> _u, std::vector <int> _v,
std::vector <int> s, std::vector <int> e, std::vector <int> l, std::vector <int> r) {
	int m = _u.size();
	int q = s.size();
	std::vector <std::vector <int>> g(n), ql(n), qr(n);
	std::vector <int> pl(q), pr(q), tord(n), initial(n), ans(q);
	Dsu dsul(n), dsur(n);
	for (int i = 0; i < m; i++) {
		g[_u[i]].push_back(_v[i]);
		g[_v[i]].push_back(_u[i]);
	}
	for (int i = 0; i < q; i++) {
		ql[l[i]].push_back(i);
		qr[r[i]].push_back(i);
	}
	for (int i = 0; i < n; i++) {
		for (int x : g[n - i - 1]) {
			if (x > n - i - 1) {
				dsul.unite(n - i - 1, x);
			}
		}
		for (int x : ql[n - i - 1]) {
			pl[x] = dsul.find(s[x]);
		}
		for (int x : g[i]) {
			if (x < i) {
				dsur.unite(i, x);
			}
		}
		for (int x : qr[i]) {
			pr[x] = dsur.find(e[x]);
		}
	}
	dsul.make(dsul.find(0));
	dsur.make(dsur.find(0));
	for (int i = 0; i < n; i++) {
		tord[dsul.tour[i]] = i;
	}
	for (int i = 0; i < n; i++) {
		initial[i] = tord[dsur.tour[i]];
	}
	Rag rag(initial);
	for (int i = 0; i < q; i++) {
		ans[i] = !!rag.query(dsur.l[pr[i]], dsur.r[pr[i]], dsul.l[pl[i]], dsul.r[pl[i]]);
	}
	return ans;
}

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