제출 #1284183

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

werewolf

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

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

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

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

int get(int y1, int y2, int cur = 1, int st = 1, int en = N){
	if (y1 >= en or y2 <= st)
		return N;
	if (y1 <= st and y2 >= en)
		return segMin[cur];

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	return min(get(y1, y2, lc, st, mid), get(y1, y2, rc, mid, en));
}


void dfs(int tp, int u, int p, int &vr){
	// cout<<tp<<"  "<<p<<" --> "<<u<<endl;
	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]));
	}

	if (nei[tp][u][0] + nei[tp][u][1] == 0){
		vr++;
	}
	else{
		dfs(tp, nei[tp][u][0], u, vr);
		dfs(tp, nei[tp][u][1], u, 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){
		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][0] = A;
		nei[0][it1][1] = B;
	}

	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;
		Min[A][0] = Min[B][0] = vl;
		nei[1][it2][0] = A;
		nei[1][it2][1] = B;
	}

	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]);
		oth[Lft[0][i]] = Lft[1][i];
	}

	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];
		}
		Quer[Lft[0][A]].push_back({Id, {A, B}});
		// ans.push_back(get(Lft[0][A], Rgt[0][A] + 1, Lft[1][B], Rgt[1][B] + 1));
	}
	ans.resize(q, 0);
	for (int i=2;i<N;i++){
		for (auto [ind, pr] : Quer[i]){
			auto [A, B] = pr;
			ans[ind] = (get(Lft[1][B], Rgt[1][B] + 1) <= Rgt[0][A]);
		}
		insert(N, oth[i]);
	}
	return ans;
}

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