제출 #465400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465400		dutch	늑대인간 (IOI18_werewolf)	C++17	0 / 100	860 ms	53652 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
#include "werewolf.h"
typedef vector<int> vi;
#define vii(Z) iota(begin(Z), end(Z), 0)
 
const int Z = 2e5;
 
int Q, k, dfsTimer;
int e[Z], r[Z], lca[2][Z], st[2*Z], tL[2][Z], tR[2][Z];
vi g[2][Z], g2[Z];

int find(int u){
	return e[u] < 0 ? u : e[u] = find(e[u]);
}
 
void dfs(int u){
	tL[k][u] = ++dfsTimer;
	for(int &v : g2[u]) dfs(v);
	tR[k][u] = dfsTimer;
}
 
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R){
	Q = size(S);
	for(int i=size(X); --i>=0; ){
		if(X[i] > Y[i]) swap(X[i], Y[i]);
		g[0][Y[i]].push_back(X[i]);
		g[1][X[i]].push_back(Y[i]);
	}
	
	vi h(size(X)); vii(h);
	vi byE(Q); vii(byE);
	vi byS(Q); vii(byS);
	int Ep = Q - 1, Sp = Q - 1;
 
	sort(begin(byS), end(byS), [&](int u, int v){ return L[u] < L[v]; });
	sort(begin(byE), end(byE), [&](int u, int v){ return R[u] > R[v]; });
 
	for(; k<2; ++k){
		iota(r, r+N, 0);
		fill(e, e+N,-1);
 
		for(int &i : h){
			if(k) while(Sp >= 0 && L[byS[Sp]] > i)
					lca[k][byS[Sp]] = r[find(S[byS[Sp]])], --Sp;
			else  while(Ep >= 0 && R[byE[Ep]] < i)
					lca[k][byE[Ep]] = r[find(E[byE[Ep]])], --Ep;

			g2[i].clear();
			int u = i;
			for(int &v : g[k][i]){
				u = find(u), v = find(v);
				if(u != v){
					g2[i].push_back(r[v]);
					if(e[u] > e[v]) swap(u, v);
					e[u] += e[v], e[v] = u;
					r[u] = r[v] = i;
				}
			}
		}
 
		if(k) for(int i=0; i<=Sp; ++i) lca[k][byS[i]] = h.back();
		else  for(int i=0; i<=Ep; ++i) lca[k][byE[i]] = h.back();
 
		dfsTimer = -1;
		dfs(h.back());
		reverse(begin(h), end(h));
	}
 
	vector<array<int, 3>> q(Q);
 
	for(int i=0; i<Q; ++i)
 		q[i] = {tL[0][lca[0][i]], tR[0][lca[0][i]], i};
 
	vi byL(N), res(Q); int pt = N-1;
	vii(byL);
	sort(begin(byL), end(byL), [&](int u, int v){
		return tL[0][u] < tL[0][v];
	});
	sort(rbegin(q), rend(q));
 
	fill(st, st+N+N, Z<<1);
	for(auto &[lx, rx, id] : q){
		while(pt >= 0 && tL[0][byL[pt]] >= lx){
			int i = tL[1][byL[pt]];
			for(st[i += N] = tL[0][byL[pt--]]; i/=2; )
				st[i] = min(st[2*i], st[2*i+1]);
		}
		int qL = tL[1][lca[1][id]], qR = tR[1][lca[1][id]], x = N+N;
		cout << lca[1][id] << endl;
 
		for(qL+=N, qR+=N+1; qL<qR; qL/=2, qR/=2){
			if(qL & 1) x = min(x, st[qL++]);
			if(qR & 1) x = min(x, st[--qR]);
		}
		res[id] = x <= rx;
	}
	return res;
}

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