제출 #381671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
381671		LucaDantas	늑대인간 (IOI18_werewolf)	C++17	100 / 100	1272 ms	242524 KiB

werewolf

#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 = 2e6+10, logn = 22;

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] = in[u] = out[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);
		if(u <= n) printf("(%d %d)\n", u, pos[u]);
		else printf("(%d [%d %d])\n", u, in[u], out[u]);
		for(int v : g[u])
			dfs_debug(v, u);
	}

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

struct Event
{
	int t, x, y1, y2, id;
	bool operator<(Event e) {
		if(x == e.x) return t<e.t; // if I'm a point I must appear before a query
		return x < e.x;
	}
} events[maxn];

struct BIT
{
	int bit[maxn];
	void upd(int x, int v) {
		for(; x < maxn; x += x&-x)
			bit[x] += v;
	}
	int query(int x) {
		int ans = 0;
		for(; x > 0; x -= x&-x)
			ans += bit[x];
		return ans;
	}
	int get(int l, int r) { return query(r) - query(l-1); }
} bit;

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 = 1; i <= N; i++)
		events[i] = {0, krt[0].pos[i], krt[1].pos[i], -1, -1};

	for(int i = 0; i < Q; i++) {
		if(S[i] < L[i] || E[i] > R[i]) ans[i] = -2*maxn;

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

		int p1 = krt[0].get(S[i], L[i], 1);
		int p2 = krt[1].get(E[i], R[i], 0);

		// printf("%d %d %d\n", i, p1, p2);


		events[N+2*i+1] = {-1, krt[0].in[p1], krt[1].in[p2], krt[1].out[p2], i},
		events[N+2*i+2] = {1, krt[0].out[p1], krt[1].in[p2], krt[1].out[p2], i};
	}

	// puts("");

	// sort(events+1, events+N+1);
	sort(events+1, events+N+2*Q+1);

	// for(int i = 1; i <= N; i++) {
	for(int i = 1; i <= N+2*Q; i++) {
		Event e = events[i];
		// printf("%d %d %d %d %d\n", e.t, e.x, e.y1, e.y2, e.id);
		if(e.t == 0) bit.upd(e.y1, 1);
		else ans[e.id] += e.t * bit.get(e.y1, e.y2);
	}

	// puts("");

	for(int i = 0; i < Q; i++)
		ans[i] = ans[i]>0;
		// printf("%d ", ans[i]), ans[i] = ans[i]>0;
	// printf("\n");

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

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