Submission #259182

#	Time	Username	Problem	Language	Result	Execution time	Memory
259182		atoiz	Werewolf (IOI18_werewolf)	C++14	100 / 100	976 ms	100712 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <functional>

using namespace std;

struct DSU
{
	int N;
	vector<int> A;
	DSU(int _N = 0): N(_N), A(N, -1) {};
	int get(int u) { return (A[u] < 0 ? u : A[u] = get(A[u])); }
	void set(int v, int u) { A[get(v)] = u; }
};

struct BIT
{
	int N;
	vector<int> A;
	BIT(int _N = 0): N(_N + 5), A(N, 0) {};
	void inc(int i)
	{
		for (; i < N; i += i & (-i)) ++A[i];
	}

	int get(int l, int r)
	{
		int ans = 0;
		for (--l; l > 0; l -= l & (-l)) ans -= A[l];
		for (; r > 0; r -= r & (-r)) ans += A[r];
		return ans;
	}
};

struct Tree : vector<vector<int>>
{
	int LG, N;
	vector<vector<int>> anc;

	Tree(int _N): N(_N) { assign(N, vector<int>()); }

	void build()
	{
		LG = __lg(N) + 1;
		anc.assign(LG, vector<int>(N, -1));
		for (int u = 0; u < N; ++u) for (int v : at(u)) anc[0][v] = u;
		for (int j = 1; j < LG; ++j) for (int u = 0; u < N; ++u) {
			anc[j][u] = (~anc[j - 1][u] ? anc[j - 1][anc[j - 1][u]] : -1);
		}
	}

	void findTour(int u, int &curTime, vector<int> &tin, vector<int> &tout)
	{
		tin[u] = ++curTime;
		for (int v : at(u)) findTour(v, curTime, tin, tout);
		tout[u] = curTime;
	}

	void solve(int u, BIT &bit, vector<vector<pair<int, int>>> &queries, vector<int> &ans, vector<int> &tin, vector<int> &tout)
	{
		for (auto &q : queries[u]) ans[q.second] = -bit.get(tin[q.first], tout[q.first]);
		bit.inc(tin[u]);
		for (int v : at(u)) solve(v, bit, queries, ans, tin, tout);
		for (auto &q : queries[u]) ans[q.second] += bit.get(tin[q.first], tout[q.first]);
	}
};

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 = (int) X.size(), Q = (int) S.size();
	vector<vector<int>> adj(N);
	for (int i = 0; i < M; ++i) adj[X[i]].push_back(i), adj[Y[i]].push_back(i);
	
	Tree startTree(N), finishTree(N);
	DSU dsu;

	dsu = DSU(N);
	for (int u = N - 1; u >= 0; --u) {
		for (int i : adj[u]) {
			int v = u ^ X[i] ^ Y[i];
			if (v > u) {
				if (dsu.get(v) == u) continue;
				// cout << "sta " << u << " -> " << dsu.get(v) << endl;
				startTree[u].push_back(dsu.get(v));
				dsu.set(v, u);
			}
		}
	}

	dsu = DSU(N);
	for (int u = 0; u < N; ++u) {
		for (int i : adj[u]) {
			int v = u ^ X[i] ^ Y[i];
			if (v < u) {
				if (dsu.get(v) == u) continue;
				// cout << "fin " << u << " -> " << dsu.get(v) << endl;
				finishTree[u].push_back(dsu.get(v));
				dsu.set(v, u);
			}
		}
	}

	finishTree.build(), startTree.build();

	vector<int> tin(N), tout(N);
	int curTime = 0;
	startTree.findTour(0, curTime, tin, tout);

	vector<vector<pair<int, int>>> queries(N);
	for (int q = 0; q < Q; ++q) {
		// cout << q << " = " << S[q] << ' ' << E[q] << endl;
		for (int j = __lg(N); j >= 0; --j) {
			if (~startTree.anc[j][S[q]] && startTree.anc[j][S[q]] >= L[q]) S[q] = startTree.anc[j][S[q]];
			if (~finishTree.anc[j][E[q]] && finishTree.anc[j][E[q]] <= R[q]) E[q] = finishTree.anc[j][E[q]];
		}
		assert(S[q] >= L[q] && E[q] <= R[q]);
		// cout << q << " = " << S[q] << ' ' << E[q] << endl;
		queries[E[q]].emplace_back(S[q], q);
	}
	BIT bit(N);
	vector<int> ans(Q, 0);
	finishTree.solve(N - 1, bit, queries, ans, tin, tout);

	// for (auto &x : ans) cout << "ans " << x << endl;
	for (auto &x : ans) x = !!x;
	return ans;
}

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