Submission #591810

#	Time	Username	Problem	Language	Result	Execution time	Memory
591810		Temmie	Werewolf (IOI18_werewolf)	C++17	15 / 100	4064 ms	24344 KiB

werewolf

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

struct Dsu {
	
	std::vector <int> p;
	
	Dsu(int size) {
		p.resize(size);
		std::iota(p.begin(), p.end(), 0);
	}
	
	inline int find(int v) {
		return v == p[v] ? v : (p[v] = find(p[v]));
	}
	
	inline void unite(int u, int v) {
		p[find(u)] = find(v);
	}
	
};

struct Sparse {
	
	std::vector <std::vector <int>> bin;
	
	std::function <int (int, int)> cmp;
	
	Sparse(const std::vector <int>& v, const std::function <int (int, int)>& _cmp) {
		cmp = _cmp;
		bin.resize(20, std::vector <int> (v.size()));
		bin[0] = v;
		for (int b = 1; b < 20; b++) {
			for (int i = 0; i < (int) v.size(); i++) {
				if (i + (1 << b) < (int) v.size()) {
					bin[b][i] = cmp(bin[b - 1][i], bin[b - 1][i + (1 << (b - 1))]);
				}
			}
		}
	}
	
	int query(int l, int r) {
		int d = r - l + 1;
		int b = 0;
		while (d) {
			b++;
			d >>= 1;
		}
		d = r - l + 1;
		return cmp(bin[b][l], bin[b][r - d + 1]);
	}
	
};

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);
	std::vector <int> deg(n, 0);
	bool sub3 = n - 1 == m;
	for (int i = 0; i < m; i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
		sub3 &= ++deg[u[i]] <= 2;
		sub3 &= ++deg[v[i]] <= 2;
	}
	if (false && sub3) {
		std::vector <int> vals;
		std::vector <int> ptrs(n);
		std::queue <int> qq;
		for (int i = 0; i < n; i++) {
			if (deg[i] == 1) {
				qq.push(i);
				break;
			}
		}
		std::vector <bool> vis(n, false);
		while (qq.size()) {
			int node = qq.front(); qq.pop();
			if (vis[node]) {
				continue;
			}
			vis[node] = true;
			ptrs[node] = vals.size();
			vals.push_back(node);
			for (int x : g[node]) {
				qq.push(x);
			}
		}
		assert(vals.size() == ptrs.size());
		Sparse sparse_mn(vals, [] (int x, int y) -> int { return std::min(x, y); });
		Sparse sparse_mx(vals, [] (int x, int y) -> int { return std::max(x, y); });
		std::vector <int> ans(q, 0);
		for (int i = 0; i < q; i++) {
			int le = std::min(ptrs[s[i]], ptrs[e[i]]);
			int ri = le ^ ptrs[s[i]] ^ ptrs[e[i]];
			int ll = le, rr = ri;
			bool yes = false;
			while (ll <= rr) {
				int mid = (ll + rr) >> 1;
				bool lok = sparse_mn.query(mid, ptrs[s[i]]) >= l[i];
				bool rok = sparse_mx.query(mid, ptrs[e[i]] <= r[i]);
				if (lok & rok) {
					yes = true;
					break;
				}
				if (!lok) {
					if (le == ptrs[s[i]]) {
						rr = mid - 1;
					} else {
						ll = mid + 1;
					}
				} else {
					if (le == ptrs[s[i]]) {
						ll = mid + 1;
					} else {
						rr = mid - 1;
					}
				}
			}
			ans[i] = yes;
		}
		return ans;
	}
	std::vector <int> ans(q, 0);
	for (int i = 0; i < q; i++) {
		Dsu dsu_l(n);
		Dsu dsu_r(n);
		for (int j = l[i]; j < n; j++) {
			for (int x : g[j]) {
				if (x >= l[i]) {
					dsu_l.unite(j, x);
				}
			}
		}
		for (int j = 0; j <= r[i]; j++) {
			for (int x : g[j]) {
				if (x <= r[i]) {
					dsu_r.unite(j, x);
				}
			}
		}
		for (int j = l[i]; j <= r[i]; j++) {
			if (dsu_l.find(s[i]) == dsu_l.find(j) && dsu_r.find(e[i]) == dsu_r.find(j)) {
				ans[i] = 1;
				break;
			}
		}
		
		//Dsu dsu(n);
		//for (int j = l[i]; j < n; j++) {
			//for (int x : g[j]) {
				//if (x >= l[i]) {
					//dsu.unite(j, x);
				//}
			//}
		//}
		//for (int j = 0; j <= r[i]; j++) {
			//for (int x : g[j]) {
				//if (x <= r[i]) {
					//dsu.unite(j, x);
				//}
			//}
		//}
		//ans[i] = dsu.find(s[i]) == dsu.find(e[i]);
	}
	return ans;
}

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