제출 #381251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
381251		LucaDantas	Werewolf (IOI18_werewolf)	C++17	15 / 100	4070 ms	114952 KiB

werewolf

#include "werewolf.h"
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;

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

struct DSU
{
	vector<int> g[maxn];
	int pai[maxn], val[maxn], p[maxn][logn], cnt;
	bool leaf[maxn];

	DSU() { for(int i = 0; i < maxn; i++) pai[i] = i; }
	void init() { for(int i = 0; i < cnt; i++) val[i] = i, leaf[i] = 1; }
	
	int find(int x) { return pai[x]==x?x:pai[x]=find(pai[x]); }
	
	void join(int a, int b, int v) {
		a = find(a), b = find(b);
		if(a == b) return;
		
		// printf("(%d %d) %d %d\n", cnt, v, a, b);
		
		g[cnt].push_back(a);
		g[cnt].push_back(b);

		val[cnt] = v;

		pai[a] = cnt;
		pai[b] = cnt;

		p[a][0] = cnt;
		p[b][0] = cnt;
		++cnt;
	}

	void dfs(int u, vector<int>& reach) {
		if(leaf[u]) return (void)(reach.push_back(u));
		for(int v : g[u])
			dfs(v, reach);
	}
} dsu, dsu2;

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

	vector<pair<int,int>> edges;

	dsu.cnt = N; dsu.init();
	dsu2.cnt = N; dsu2.init();
	int M = (int)(X.size());
	for(int i = 0; i < M; i++) {
		if(X[i] > Y[i]) swap(X[i], Y[i]);
		edges.push_back({X[i], Y[i]});
	}

	sort(edges.begin(), edges.end(), [](pair<int,int> a, pair<int,int> b) {
		return a.first > b.first;
	});

	for(int i = 0; i < M; i++) {
		int a = edges[i].first, b = edges[i].second;
		dsu.join(a, b, a); // a já é o minimo
	}

	// puts("");

	// Do the same but using the bigger edge now in increasing order
	sort(edges.begin(), edges.end(), [](pair<int,int> a, pair<int,int> b) {
		return a.second < b.second;
	});

	for(int i = 0; i < M; i++) {
		int a = edges[i].first, b = edges[i].second;
		dsu2.join(a, b, b);
	}

	// puts("");
	// brute force to check if my krt works

	int Q = S.size();
	vector<int> ans(Q);

	// vector<int> go;
	// dsu2.dfs(5, go);
	// for(int x : go)
	// 	printf("%d ", x);
	// printf("\n");

	for(int i = 0; i < Q; i++) {
		int v = E[i];
		if(v > R[i]) continue;
		while(dsu2.p[v][0] && dsu2.val[dsu2.p[v][0]] <= R[i])
			v = dsu2.p[v][0]; // too lazy to do binary lifting

		vector<int> reach1; dsu2.dfs(v, reach1);
		sort(reach1.begin(), reach1.end());

		// printf("R1 %d %d\n", S[i], v);
		// for(int x : reach1)
		// 	printf("%d ", x);
		// printf("\n");

		v = S[i];
		if(v < L[i]) continue;
		while(dsu.p[v][0] && dsu.val[dsu.p[v][0]] >= L[i])
			v = dsu.p[v][0];

		vector<int> reach2; dsu.dfs(v, reach2);

		// printf("R2 %d %d\n", E[i], v);
		// for(int x : reach2)
		// 	printf("%d ", x);
		// printf("\n");

		bool ok = 0;
		for(int i = 0; i < (int)reach2.size(); i++)
			ok |= binary_search(reach1.begin(), reach1.end(), reach2[i]);

		ans[i] = ok;
	}

	return ans;
}

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