Submission #381280

#	Time	Username	Problem	Language	Result	Execution time	Memory
381280		LucaDantas	Werewolf (IOI18_werewolf)	C++17	15 / 100	4011 ms	119072 KiB

werewolf

// The other code was too messy, testing the new brute (with binary lifting)
#include "werewolf.h"
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;

using pii = pair<int,int>;

#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ff first
#define ss second

constexpr int maxn = 4e5+10, logn = 20;

int n;

struct DSU
{
	int pai[maxn];
	DSU() { for(int i = 0; i < maxn; i++) pai[i] = i; }
	void init() { for(int i = 0; i < maxn; i++) pai[i] = i; }
	int find(int x) { return pai[x]==x?x:pai[x]=find(pai[x]); }
	bool join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return 0;
		pai[b] = a;
		return 1;
	}
} dsu;

struct KRT
{
	vector<int> g[maxn]; // graph pointing down
	int tab[maxn][logn], val[maxn], pos[maxn], head = 0, t = 1; // position of leafs

	int in[maxn], out[maxn];

	DSU aux;

	void addEdge(int from, int to, int weight) {
		head = from;
		val[from] = weight;

		to = aux.find(to); // gets the head of the component
		aux.join(from, to); // make him my son

		tab[to][0] = from;
		g[from].pb(to);
	}

	void dfs(int u) {
		if(u <= n) return (void)(pos[u] = t++);

		in[u] = t;
		for(int v : g[u])
			dfs(v);
		out[u] = t-1;
	}

	void build() {
		dfs(head);

		for(int l = 1; l < logn; l++)
			for(int i = 1; i <= head; i++)
				tab[i][l] = tab[tab[i][l-1]][l-1];
	}

	int get(int u, int v, int k) {
		auto comp = [&](int a, int b) { return k?a>=b:a<=b; };
		for(int l = logn-1; l >= 0; l--) {
			if(tab[u][l] && comp(val[tab[u][l]], v))
				u = tab[u][l];
		}
		return u;
	}

	void get_dfs(int u, vector<int>& vv) {
		if(u <= n) return (void)(vv.pb(u));
		for(int v : g[u])
			get_dfs(v, vv);
	}

	void dfs_debug(int u, int p) {
		printf("%d %d\n", u, p);
		// printf("(%d %d) <- %d\n", u, pos[u], p);
		// printf("(%d [%d %d]) <- %d\n", u, in[u], out[u], p);
		for(int v : g[u])
			dfs_debug(v, u);
	}

	void debug() {
		puts("PRINTING THE TREE");
		dfs_debug(head, 0);
	}
} krt[2];

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
	vector<int> S, vector<int> E, vector<int> L, vector<int> R) {

	n = N;

	vector<pii> edges;
	int M = (int)X.size();
	for(int i = 0; i < M; i++) {
		if(X[i] > Y[i]) swap(X[i], Y[i]);
		++X[i], ++Y[i];

		edges.pb({X[i], Y[i]});
	}


	{
		sort(all(edges), [](pii a, pii b) {
			return a.first > b.first;
		});

		int cnt = N;
		for(int i = 0; i < M; i++) {
			int a = edges[i].ff, b = edges[i].ss;
			// puts("OI");
			if(dsu.join(a, b)) {
				// printf("%d %d\n", a, b);
				++cnt;
				krt[0].addEdge(cnt, a, a); // from, to, value of new node
				krt[0].addEdge(cnt, b, a);
			}
		}

		krt[0].build();

		// krt[0].debug();
	}

	{
		dsu.init();

		// Sort by increasing big value
		sort(all(edges), [](pii a, pii b) {
			return a.ss < b.ss;
		});

		int cnt = N;
		for(int i = 0; i < M; i++) {
			int a = edges[i].ff, b = edges[i].ss;
			if(dsu.join(a, b)) {
				++cnt;
				krt[1].addEdge(cnt, a, b);
				krt[1].addEdge(cnt, b, b);
			}
		}

		krt[1].build();

		// krt[1].debug();
	}

	int Q = S.size();

	vector<int> ans(Q);

	for(int i = 0; i < Q; i++) {
		if(S[i] < L[i] || E[i] > R[i]) continue;

		++S[i], ++E[i], ++L[i], ++R[i];

		vector<int> r1; krt[0].get_dfs(krt[0].get(S[i], L[i], 1), r1);
		vector<int> r2; krt[1].get_dfs(krt[1].get(E[i], R[i], 0), r2);

		sort(all(r1));

		for(int j = 0; j < (int)r2.size(); j++)
			ans[i] |= binary_search(all(r1), r2[j]);
	}

	return ans;
	// return vector<int>(0);
}

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