제출 #1029744

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

werewolf

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 4;
const int maxs = 4 * maxn;
const int oo = 1e9 + 7;

int n, m, q;
vector<int> adj[maxn], adjx[maxs];
int val1, val2, sz, p[maxs], A[maxs];
vector<pii> Q1[maxs], Q2[maxs];
int R1[maxn], R2[maxn]; set<int> gooni[maxs];
int st[maxs], ft[maxs], timer = 0;
vector<pair<pii, int>> Q[maxs];
vector<pii> G1, G2; vector<int> res;

int get(int a) {
	return (p[a] == a) ? a : p[a] = get(p[a]);
}

void merge(int a, int b, int x) {
	a = get(a); b = get(b);
	if (a == b) return ;
	int v = sz++; A[v] = x;
	p[v] = v; p[a] = v; p[b] = v;
	adjx[v].pb(a); adjx[v].pb(b);
}

void dfs(int v, bool time) {
	if (time) st[v] = timer++;
	G1.pb(Mp(A[v], v)); G2.pb(Mp(-A[v], v));
	
	for (auto f : Q1[v]) {
		int j = lower_bound(all(G1), Mp(f.F, -oo)) - G1.begin();
		R1[f.S] = G1[j].S;
	}
	for (auto f : Q2[v]) {
		int j = lower_bound(all(G2), Mp(-f.F, -oo)) - G2.begin();
		R2[f.S] = G2[j].S;
	}
	
	for (int u : adjx[v]) {
		dfs(u, time);
	}
	
	G1.pop_back(); G2.pop_back();
	if (time) ft[v] = timer;
}

void sack(int v) {
	if (len(adjx[v]) == 0) gooni[v].insert(st[v]);
	for (int u : adjx[v]) {
		sack(u);
		if (len(gooni[u]) > len(gooni[v])) swap(gooni[u], gooni[v]);
		for (int x : gooni[u]) gooni[v].insert(x);
		gooni[u].clear();
	}
	for (auto f : Q[v]) {
		int l = f.F.F, r = f.F.S, j = f.S;
		auto it = gooni[v].lower_bound(l);
		if (it != gooni[v].end() && (*it) < r) res[j] = 1;
		else res[j] = 0;
	}
}

vector<int> check_validity(int Nx, vector<int> ux, vector<int> vx,
								vector<int> sx, vector<int> ex,
								vector<int> lx, vector<int> rx) {
	n = Nx; m = len(ux); q = len(sx);
	for (int i = 0; i < m; i++) {
		int u = ux[i], v = vx[i];
		adj[u].pb(v); adj[v].pb(u);
	}
	
	val1 = 0; sz = val1 + n;
	iota(p + val1, p + sz, val1);
	iota(A + val1, A + sz, 0);
	for (int i = n - 1; i >= 0; i--) {
		for (int j : adj[i]) {
			if (j > i) merge(i + val1, j + val1, i);
		}
	}
	int v1 = sz - 1;
	
	val2 = sz; sz = val2 + n;
	iota(p + val2, p + sz, val2);
	iota(A + val2, A + sz, 0);
	for (int i = 0; i < n; i++) {
		for (int j : adj[i]) {
			if (j < i) merge(i + val2, j + val2, i);
		}
	}
	int v2 = sz - 1;
	
	for (int i = 0; i < q; i++) {
		int s = sx[i], e = ex[i];
		int l = lx[i], r = rx[i];
		Q1[s + val1].pb(Mp(l, i));
		Q2[e + val2].pb(Mp(r, i));
	}
	
	dfs(v1, 1); dfs(v2, 0);
	for (int v = val2; v < val2 + n; v++) st[v] = st[v - val2];
	
	res.resize(q);
	for (int i = 0; i < q; i++) {
		int u1 = R1[i], u2 = R2[i];
		Q[u2].pb(Mp(Mp(st[u1], ft[u1]), i));
	}
	sack(v2);
	return res;
}

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