제출 #1284153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284153		Jawad_Akbar_JJ	늑대인간 (IOI18_werewolf)	C++20	49 / 100	4108 ms	416488 KiB

werewolf

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "werewolf.h"

using namespace std;
const int N = (1<<19) + 1;
set<int> Set[N<<1];
vector<int> nei[2][N], ans;
int Lft[2][N], Rgt[2][N], Par[2][N][20], par[2][N], Min[N][20], Max[N][20];

void insert(int x, int y, int cur = 1, int st = 1, int en = N){
	if (x >= en or x < st)
		return;
	Set[cur].insert(y);
	if (en - st == 1)
		return;

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	insert(x, y, lc, st, mid);
	insert(x, y, rc, mid, en);
}

int get(int x1, int x2, int y1, int y2, int cur = 1, int st = 1, int en = N){
	if (x1 >= en or x2 <= st)
		return 0;
	if (x1 <= st and x2 >= en)
		return Set[cur].upper_bound(y1 - 1) != Set[cur].upper_bound(y2 - 1);
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	return get(x1, x2, y1, y2, lc, st, mid) | get(x1, x2, y1, y2, rc, mid, en);
}


void dfs(int tp, int u, int p, int &vr){
	Lft[tp][u] = vr;

	Par[tp][u][0] = p;
	for (int i=1;i<=18;i++){
		Par[tp][u][i] = (Par[tp][u][i-1] == -1 ? -1 : Par[tp][Par[tp][u][i-1]][i-1]);
		if (tp == 0)
			Max[u][i] = max(Max[u][i-1], (Par[tp][u][i-1] == -1 ? N : Max[Par[tp][u][i-1]][i-1]));
		else
			Min[u][i] = min(Min[u][i-1], (Par[tp][u][i-1] == -1 ? -1 : Min[Par[tp][u][i-1]][i-1]));
	}
	for (int i : nei[tp][u])
		dfs(tp, i, u, vr);

	
	if (nei[tp][u].size() == 0)
		vr++;
	Rgt[tp][u] = vr - 1;
}

int root(int tp, int v){
	return (par[tp][v] == 0 or par[tp][v] == v ? v : par[tp][v] = root(tp, par[tp][v]));
}

vector<int> check_validity(int n, vector<int> U, vector<int> V, vector<int> X, vector<int> Y, vector<int> L, vector<int> R){
	int m = U.size(), q = L.size(), it1 = n - 1, it2 = n - 1, vr = 2;

	vector<pair<int,int>> E1, E2;
	for (int i=0;i<m;i++){
		E1.push_back({max(U[i], V[i]), i});
		E2.push_back({min(U[i], V[i]), i});
	}

	sort(begin(E1), end(E1));
	sort(rbegin(E2), rend(E2));

	for (auto [vl, id] : E1){
		// cout<<U[id]<<" "<<V[id]<<" "<<vl<<endl;
		int A = root(0, U[id]), B = root(0, V[id]);
		if (A == B)
			continue;
		par[0][A] = par[0][B] = ++it1;
		Max[A][0] = Max[B][0] = vl;
		nei[0][it1].push_back(A);
		nei[0][it1].push_back(B);
		// cout<<it1<<" "<<A<<" "<<vl<<endl;
		// cout<<it1<<" "<<B<<" "<<vl<<endl;
	}

	// cout<<endl<<endl;
	// return L;

	for (auto [vl, id] : E2){
		int A = root(1, U[id]), B = root(1, V[id]);
		if (A == B)
			continue;
		par[1][A] = par[1][B] = ++it2;
		Par[1][A][0] = Par[1][B][0] = it2;
		Min[A][0] = Min[B][0] = vl;
		nei[1][it2].push_back(A);
		nei[1][it2].push_back(B);
		// cout<<it2<<" "<<A<<" "<<vl<<endl;
		// cout<<it2<<" "<<B<<" "<<vl<<endl;
	}
	// cout<<endl<<endl;
	dfs(0, it1, -1, vr);
	vr = 2;
	dfs(1, it2, -1, vr);

	for (int i=0;i<n;i++){
		insert(Lft[0][i], Lft[1][i]);
		// cout<<Lft[0][i]<<" "<<Lft[1][i]<<endl;
	}
	// cout<<endl;

	for (int Id=0;Id<q;Id++){
		int B = X[Id], A = Y[Id];

		for (int i=18;i>=0;i--){
			if (Par[0][A][i] != -1 and Max[A][i] <= R[Id])
				A = Par[0][A][i];

			if (Par[1][B][i] != -1 and Min[B][i] >= L[Id])
				B = Par[1][B][i];
		}

		// cout<<A<<" "<<B<<' ';
		ans.push_back(get(Lft[0][A], Rgt[0][A] + 1, Lft[1][B], Rgt[1][B] + 1));
		// cout<<ans.back()<<'\n';
		// cout<<Lft[0][A]<<" "<<Rgt[0][A]<<" "<<Lft[1][B]<<" "<<Rgt[1][B]<<endl;
	}
	return ans;
}

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