제출 #312926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
312926		reymontada61	늑대인간 (IOI18_werewolf)	C++14	100 / 100	2594 ms	218144 KiB

werewolf

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

int n, m;
const int MXN = 400005, MXK = 20;
int par[MXN][2];

int nextnode[2];
vector<int> subs[MXN][2];

int value[MXN][2];

int parent(int w, int n) {
	if (par[n][w] == n) return n;
	return par[n][w] = parent(w, par[n][w]);
}

void connect(int w, int a, int b, int val) {
	a = parent(w, a);
	b = parent(w, b);
	if (a == b) return;
	int c = nextnode[w];
	nextnode[w]++;
	par[a][w] = c;
	par[b][w] = c;
	subs[c][w].push_back(a);
	subs[c][w].push_back(b);
}

int prk[MXN][MXK][2];
pair<int, int> bounds[MXN][2];
int offer[MXN];
int posof[MXN][2];

pair<int, int> dfs(int node, int par, int w) {
	int mn = INT_MAX, mx = INT_MIN;
	prk[node][0][w] = par;
	for (int i=1; i<MXK; i++) {
		int t = prk[node][i-1][w];
		if (t != -1) {
			prk[node][i][w] = prk[t][i-1][w];
		}
	}
	if (w == 0) value[node][w] = INT_MAX;
	else value[node][w] = INT_MIN;
	for (auto x: subs[node][w]) {
		pair<int, int> t = dfs(x, node, w);
		if (w == 0) value[node][w] = min(value[node][w], value[x][w]);
		else value[node][w] = max(value[node][w], value[x][w]);
		mn = min(mn, t.first);
		mx = max(mx, t.second);
	}
	if (mn == INT_MAX) {
		value[node][w] = node;
		offer[w]++;
		posof[node][w] = offer[w]-1;
		return bounds[node][w] = {offer[w]-1, offer[w]-1};
	}
	return bounds[node][w] = {mn, mx};
}

int highest(int n, int w, int minok, int maxok) {
	for (int i=MXK-1; i>=0; i--) {
		int t = prk[n][i][w];
		if (t != -1 && value[t][w] >= minok && value[t][w] <= maxok) {
			n = t;
		}
	}
	return n;
}

vector<pair<int, int>> points;

vector<int> contents[MXN * 4];

void build(int ind, int l, int r) {
	if (l == r) {
		contents[ind].push_back(points[l].second);
		return;
	}
	int m = (l + r) / 2;
	build(ind * 2, l, m);
	build(ind * 2 + 1, m+1, r);
	int lp = 0, rp = 0;
	while (lp < contents[ind * 2].size() && rp < contents[ind * 2 + 1].size()) {
		if (contents[ind*2][lp] < contents[ind*2+1][rp]) {
			contents[ind].push_back(contents[ind*2][lp]);
			lp++;
		}
		else {
			contents[ind].push_back(contents[ind*2+1][rp]);
			rp++;
		}
	}
	while (lp < contents[ind * 2].size()) {
		contents[ind].push_back(contents[ind*2][lp]);
		lp++;
	}
	while (rp < contents[ind * 2 + 1].size()) {
		contents[ind].push_back(contents[ind*2+1][rp]);
		rp++;
	}
}

int query(int ind, int l, int r, int ql, int qr, int ml, int mr) {
	if (ql <= l && r <= qr) {
		return lower_bound(contents[ind].begin(), contents[ind].end(), ml) != upper_bound(contents[ind].begin(), contents[ind].end(), mr);
	}
	if (ql > r || qr < l) {
		return 0;
	}
	int m = (l + r) / 2;
	return query(ind * 2, l, m, ql, qr, ml, mr) + query(ind * 2 + 1, m+1, r, ql, qr, ml, mr);
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	
	n = N;
	
	nextnode[0] = nextnode[1] = n;
	
	for (int i=0; i<MXN; i++) {
		par[i][0] = par[i][1] = i;
	}
	
	for (int i=0; i<n; i++) {
		value[i][0] = value[i][1] = i;
	}

	int Q = S.size();
	vector<int> A;
	int M = X.size();
	
	m = M;
	
	vector<pair<int, pair<int, int>>> minproc, maxproc;
	
	for (int i=0; i<M; i++) {
		int a = X[i], b = Y[i];
		minproc.push_back({min(a, b), {a, b}});
		maxproc.push_back({max(a, b), {a, b}});
	}
	
	sort(minproc.begin(), minproc.end());
	reverse(minproc.begin(), minproc.end());
	sort(maxproc.begin(), maxproc.end());
	
	for (auto x: minproc) {
		int v = x.first;
		int a = x.second.first, b = x.second.second;
		connect(0, a, b, v);
	}
	
	for (auto x: maxproc) {
		int v = x.first;
		int a = x.second.first, b = x.second.second;
		connect(1, a, b, v);
	}
	
	for (int i=0; i<MXN; i++) {
		for (int j=0; j<MXK; j++) {
			prk[i][j][0] = prk[i][j][1] = -1;
		}
	}
	
	dfs(2 * n - 2, -1, 0);
	dfs(2 * n - 2, -1, 1);
	
	for (int i=0; i<n; i++) {
		int x = posof[i][0], y = posof[i][1];
		points.push_back({x, y});
	}
	
	sort(points.begin(), points.end());
	
	build(1, 0, n-1);
	
	for (int i=0; i<Q; i++) {
		
		int s = S[i], e = E[i], l = L[i], r = R[i];
		
		int side = highest(s, 0, l, n-1);
		int other = highest(e, 1, 0, r);
		
		A.push_back(query(1, 0, n-1, bounds[side][0].first, bounds[side][0].second, bounds[other][1].first, bounds[other][1].second) > 0);
		
	}
	
	return A;
	
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:86:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  while (lp < contents[ind * 2].size() && rp < contents[ind * 2 + 1].size()) {
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:86:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  while (lp < contents[ind * 2].size() && rp < contents[ind * 2 + 1].size()) {
      |                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:96:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  while (lp < contents[ind * 2].size()) {
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:100:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  while (rp < contents[ind * 2 + 1].size()) {
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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