oj.uz

답안 #465387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465387 2021-08-15T19:37:57 Z dutch 늑대인간 (IOI18_werewolf) C++17
0 / 100
 457 ms 28528 KB 
#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 NL = 2e5, ML = 6e5, LOG = 21;

int N, M, Q, k, dfsTimer;
int e[NL], r[NL], lca[2][NL], st[2*NL], tL[2][ML], tR[2][ML];
array<int, 2> g[ML];

int find(int u){
	return e[u] < 0 ? u : e[u] = find(e[u]);
}

void dfs(int u){
	if(u < N){
		tL[k][u] = ++dfsTimer;
	}else{
		tL[k][u] = 1+dfsTimer;
		auto &[vL, vR] = g[u-N];
		dfs(vL);
		if(vL != vR) dfs(vR);	
	}
	tR[k][u] = dfsTimer;
}

vi check_validity(int __N, vi X, vi Y, vi S, vi E, vi L, vi R){
	N = __N, Q = size(S), M = size(X);
	for(int i=0; i<M; ++i)
		if(X[i] > Y[i]) swap(X[i], Y[i]);
	
	vi h(M); vii(h);
	vi byE(Q); vii(byE);
	vi byS(Q); vii(byS);

	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){
		sort(begin(h), end(h), [&](int &u, int &v){
			return k ? X[u] > X[v] : Y[u] < Y[v];
		});
		iota(r, r+N, 0);
		fill(e, e+N,-1);

		for(int &i : h){
			int u = find(X[i]), v = find(Y[i]);

			if(k) while(!empty(byS) && L[byS.back()] > X[i]){
					lca[k][byS.back()] = r[find(S[byS.back()])];
					byS.pop_back();
			}else while(!empty(byE) && R[byE.back()] < Y[i]){
					lca[k][byE.back()] = r[find(E[byE.back()])];
					byE.pop_back();
			}

			if(e[u] > e[v]) swap(u, v);
			g[i] = {r[u], r[v]};
			if(u != v){
				e[u] += e[v];
				e[v] = u;
			}
			r[u] = i+N;
		}

		if(k) for(int &i : byS) lca[k][i] = h.back();
		else  for(int &i : byE) lca[k][i] = h.back();

		dfsTimer = -1;
		dfs(h.back()+N);
	}

	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, ML);
	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]);
			--pt;
		}
		int qL = tL[1][lca[1][id]], qR = tR[1][lca[1][id]], x = N+N;

		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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 457 ms 28528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -