제출 #114104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114104		arman_ferdous	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4035 ms	88844 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
const int N = 2e5+10;

int n, m, q;
int st[2][N], ft[2][N], p[2][18][N];
vi UU[N], DD[N], t[2][N], eul[2];

int dsu[N];
void init() {
	for(int i = 0; i < n; i++)
		dsu[i] = i;
}
int find(int x) {
	if(dsu[x] == x) return x;
	return dsu[x] = find(dsu[x]);
}

void dfs(int u, int id) {
	st[id][u] = eul[id].size();
	eul[id].push_back(u);
	for(int v : t[id][u]) 
		dfs(v, id);
	ft[id][u] = eul[id].size()-1;
}

set<int> bf;
vi ans;
vi check_validity(int _n, vi X, vi Y, vi S, vi E, vi L, vi R) {
	n = _n;
	m = X.size();
	q = S.size();

	for(int i = 0; i < m; i++) {
		if(X[i] > Y[i]) swap(X[i], Y[i]);
		UU[X[i]].push_back(Y[i]);
		DD[Y[i]].push_back(X[i]);
	}

	memset(p,-1,sizeof p);
	init();
	for(int i = 0; i < n; i++) {
		for(int v : DD[i]) {
			int par = find(v);
			if(par == i) continue;
			t[1][i].push_back(par);
			// cout << "low " << i << " --> " << par << endl;
			p[1][0][par] = i;
			dsu[par] = i;
		}
	}
	init();
	for(int i = n-1; i >= 0; i--) {
		for(int v : UU[i]) {
			int par = find(v);
			if(par == i) continue;
			t[0][i].push_back(par);
			// cout << "big " << i << " --> " << par << endl;
			p[0][0][par] = i;
			dsu[par] = i;
		}
	}
	dfs(0,0);
	dfs(n-1,1);

	// for(int i = 0; i < n; i++)
	// 	cout << eul[0][i] << " "; cout << endl;
	// for(int i = 0; i < n; i++)
	// 	cout << eul[1][i] << " "; cout << endl;

	for(int id : {0,1}) 
		for(int j = 1; j < 18; j++)
			for(int i = 0; i < n; i++)
				if(p[id][j-1][i] != -1) 
					p[id][j][i] = p[id][j-1][p[id][j-1][i]];

	for(int Q = 0; Q < q; Q++) {
		// cout << "Query = " << S[Q] << " ---> " << E[Q] << ",,,, L = " << L[Q] << " R = " << R[Q] << endl;
		int U = S[Q], V = E[Q];
		for(int j = 17; j >= 0; j--) {
			if(p[0][j][U] != -1 && L[Q] <= p[0][j][U]) U = p[0][j][U];
			if(p[1][j][V] != -1 && p[1][j][V] <= R[Q]) V = p[1][j][V];
		}
		// cout << "query union in " << U << " and " << V << "'s subtree\n";
		bf.clear();
		int found = 0;
		for(int i = st[0][U]; i <= ft[0][U]; i++)
			bf.insert(eul[0][i]);
		for(int i = st[1][V]; i <= ft[1][V]; i++)
			if(bf.find(eul[1][i]) != bf.end())
				found++;
		if(found) ans.push_back(1);
		else ans.push_back(0);
	}
	return ans;
}

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