Submission #1166627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166627		xnqs	Werewolf (IOI18_werewolf)	C++17	0 / 100	742 ms	163936 KiB

werewolf

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include "werewolf.h"
#include <cassert>
#include <functional>

template<typename Type>
class FenwickTree {
private:
	std::vector<Type> bit;
public:
	FenwickTree(int size = 0, Type val = 0) {
		Assign(size, val);
	}

	void Assign(int size = 0, Type val = 0) {
		bit.assign(size+1, 0);
		if (size&&val) {
			for (int i = 1; i < bit.size(); i++) {
				bit[i] += val;
				if (i+(i&-i)<bit.size()) {
					bit[i+(i&-i)] += bit[i];
				}
			}
		}
	}

	void Add(int pos, Type val) {
		while (pos < bit.size()) {
			bit[pos] += val;
			pos += pos&-pos;
		}
	}

	Type Query(int pos) {
		Type ret = 0;
		while (pos > 0) {
			ret += bit[pos];
			pos ^= pos&-pos;
		}
		return ret;
	}

	Type Query(int l, int r) {
		return Query(r) - Query(l-1);
	}
};

class DSU {
private:
	std::vector<int> t;
	std::vector<int> sz;
public:
	DSU(int n = 0) {
		t.assign(n, 0); std::iota(t.begin(),t.end(),0);
		sz.assign(n, 1);
	}

	int Find(int k) {
		if (t[k]!=k) return t[k] = Find(t[k]);
		return t[k];
	}

	int Unite(int a, int b) {
		a = Find(a);
		b = Find(b);
		
		if (a==b) {
			return 0;
		}
		if (sz[a]<sz[b]) {
			std::swap(a,b);
		}

		sz[a] += sz[b];
		t[b] = a;
		return 1;
	}

	int UniteExplicit(int a, int b) {
		a = Find(a);
		b = Find(b);
		
		if (a==b) {
			return 0;
		}

		sz[a] += sz[b];
		t[b] = a;
		return 1;
	}
};

struct Query {
	int l, r, pfx, idx, sgn;
	Query():
		l(0), r(0), pfx(0), idx(0), sgn(0) {}
	Query(int l, int r, int pfx, int idx, int sgn):
		l(l), r(r), pfx(pfx), idx(idx), sgn(sgn) {}
};

int gs, q;
std::vector<std::vector<int>> adj_list;

std::vector<std::vector<int>> krt_less;
std::vector<int> krt_less_tour;
int krt_less_label[400005];
int krt_less_tin[400005];
int krt_less_tout[400005];
int krt_less_depth[400005];
int krt_less_up[19][400005];

std::vector<std::vector<int>> krt_greater;
std::vector<int> krt_greater_tour;
int krt_greater_label[400005];
int krt_greater_tin[400005];
int krt_greater_tout[400005];
int krt_greater_depth[400005];
int krt_greater_up[19][400005];

void build_krts() {
	// less
	std::vector<bool> active(gs+1, 0);
	DSU dsu(2*gs+5);
	for (int i = 0, timer = gs; i < gs; i++) {
		active[i] = 1;
		for (const auto& j : adj_list[i]) {
			if (active[j]) {
				int ri = dsu.Find(i);
				int rj = dsu.Find(j);

				if (ri!=rj) {
					dsu.UniteExplicit(timer, ri);
					dsu.UniteExplicit(timer, rj);
					krt_less[timer].emplace_back(ri);
					krt_less[timer].emplace_back(rj);
					krt_less_label[timer] = i;
					//std::cout << timer << " " << krt_less_label[timer] << " " << ri << "\n";
					//std::cout << timer << " " << krt_less_label[timer] << " " << rj << "\n";
					++timer;
				}
			}
		}
	}

	// greater
	active.assign(gs+1, 0);
	dsu = DSU(2*gs+5);
	for (int i = gs-1, timer = gs; i >= 0; i--) {
		active[i] = 1;
		for (const auto& j : adj_list[i]) {
			if (active[j]) {
				int ri = dsu.Find(i);
				int rj = dsu.Find(j);

				if (ri!=rj) {
					//std::cout << timer << " " << ri << "\n";
					//std::cout << timer << " " << rj << "\n";
					dsu.UniteExplicit(timer, ri);
					dsu.UniteExplicit(timer, rj);
					krt_greater[timer].emplace_back(ri);
					krt_greater[timer].emplace_back(rj);
					krt_greater_label[timer] = i;
					//std::cout << timer << " " << krt_greater_label[timer] << " " << ri << "\n";
					//std::cout << timer << " " << krt_greater_label[timer] << " " << rj << "\n";
					++timer;
				}
			}
		}
	}
}

void process_krts() {
	const std::function<void(int, std::vector<std::vector<int>>&, std::vector<int>&, int*, int*, int*, int[19][400005])>
	dfs = [&](int k, std::vector<std::vector<int>>& adj, std::vector<int>& tour, int* tin, int* tout, int* depth, int up[19][400005]) {
		//std::cout << k << "\n";
		tour.emplace_back(k);
		tin[k] = tour.size()-1;
		for (const auto& i : adj[k]) {
			depth[i] = depth[k]+1;
			up[0][i] = k;
			for (int j = 1; j < 19; j++) {
				up[j][i] = ((up[j-1][i]!=-1) ? up[j-1][up[j-1][i]] : -1);
			}
			dfs(i, adj, tour, tin, tout, depth, up);
		}
		
		tout[k] = tour.size()-1;
	};

	krt_less_up[0][2*gs-2] = -1;
	dfs(2*gs-2, krt_less, krt_less_tour, krt_less_tin, krt_less_tout, krt_less_depth, krt_less_up);
	
	krt_greater_up[0][2*gs-2] = -1;
	dfs(2*gs-2, krt_greater, krt_greater_tour, krt_greater_tin, krt_greater_tout, krt_greater_depth, krt_greater_up);
}

int root_search_less(int node, int tgt) {
	for (int step = 18; step >= 0; step--) {
		if (krt_less_up[step][node] != -1 && (1<<step) <= krt_less_depth[node] && krt_less_label[krt_less_up[step][node]] <= tgt) {
			node = krt_less_up[step][node];
		}
	}
	return node;
}

int root_search_greater(int node, int tgt) {
	for (int step = 18; step >= 0; step--) {
		if (krt_greater_up[step][node] != -1 && (1<<step) <= krt_greater_depth[node] && krt_greater_label[krt_greater_up[step][node]] >= tgt) {
			node = krt_greater_up[step][node];
		}
	}
	return node;
}

std::vector<int> solve_queries(std::vector<Query> queries) {
	std::sort(queries.begin(),queries.end(),[](const Query& a, const Query& b) {
		return a.pfx < b.pfx;
	});

	std::vector<int> ret(q, 0);
	std::vector<int> pos(2*gs+5, -1);
	for (int i = 0; i < krt_greater_tour.size()-1; i++) {
		if (krt_greater_tour[i] < gs) {
			pos[krt_greater_tour[i]] = i;
		}
	}

	int scanline = 0;
	FenwickTree<int> fnwk(2*gs+5, 0);
	for (const auto& [ql, qr, qpfx, qidx, qsgn] : queries) {
		while (scanline <= qpfx) {
			if (pos[krt_less_tour[scanline]]!=-1 && krt_less_tour[scanline] < gs) {
				//std::cout << scanline << " " << pos[krt_less_tour[scanline]] << "\n";
				fnwk.Add(pos[krt_less_tour[scanline]]+1, 1);
			}
			++scanline;
		}

		//std::cout << ql << " " << qr << " " << qpfx << " " << qidx << " " << qsgn << " " << fnwk.Query(ql+1,qr+1) << "\n";
		ret[qidx] += qsgn * fnwk.Query(ql+1, qr+1);
	}

	return ret;
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	gs = N;
	q = S.size();
	adj_list.resize(gs+1);
	krt_less.resize(2*gs+5);
	krt_greater.resize(2*gs+5);

	for (int i = 0; i < gs-1; i++) {
		adj_list[X[i]].emplace_back(Y[i]);
		adj_list[Y[i]].emplace_back(X[i]);
	}

	build_krts();
	process_krts();

	/*for (const auto& i : krt_less_tour) {
		std::cout << i << " ";
	}
	std::cout << "\n";
	for (int i = 0; i < 2*gs-1; i++) {
		std::cout << krt_less_tin[i] << " " << krt_less_tout[i] << "\n";
	}*/

	/*for (const auto& i : krt_less_tour) {
		std::cout << i << " ";
	}
	std::cout << "\n";*/

	std::vector<Query> queries;
	for (int i = 0; i < S.size(); i++) {
		int root_human = root_search_greater(S[i], L[i]);
		int root_wolf = root_search_less(E[i], R[i]);

		int l1 = krt_greater_tin[root_human], r1 = krt_greater_tout[root_human];
		int l2 = krt_less_tin[root_wolf], r2 = krt_less_tout[root_wolf];

		/*if (l1 == r1 && krt_greater_tour[l1] < gs) {
			continue;
		}
		if (l2 == r2 && krt_less_tour[l2] < gs) {
			continue;
		}*/

		queries.emplace_back(l1,r1,r2,i,1);
		if (l2-1>=0) {
			queries.emplace_back(l1,r1,l2-1,i,-1);
		}

		//std::cout << root_human << " " << root_wolf << "\n";
		//std::cout << l1 << " " << r1 << " " << l2 << " " << r2 << "\n";
	}

	std::vector<int> ret = solve_queries(queries);
	for (int i = 0; i < ret.size(); i++) {
		ret[i] = !!ret[i];
	}
	return ret;
}

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