Submission #404354

#	Time	Username	Problem	Language	Result	Execution time	Memory
404354		SeDunion	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4070 ms	190624 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif
using namespace std;
using ll = long long;
const int MAXN = 1e6 + 11;
int N, Q, M;

int P[MAXN], sz, par[MAXN], val[MAXN], go[MAXN][2];
int getP(int a) {
	if (a == P[a]) return a;
	return P[a] = getP(P[a]);
}
vector<int>g[MAXN];

int L[MAXN], R[MAXN];

vector<int>G[2];

void dfs(int v, int t) {
	if (!go[v][0] && !go[v][1]) {
		L[v] = R[v] = G[t].size();
		cerr << v << " " << t << " " << L[v] << " " << R[v] << endl;
		G[t].emplace_back(v);
		return;
	}
	dfs(go[v][0], t);
	dfs(go[v][1], t);
	L[v] = L[go[v][0]];
	R[v] = R[go[v][1]];
	cerr << v << " " << t << " " << L[v] << " " << R[v] << endl;
}

vector<int>tv[MAXN << 2];

void build(int l = 0, int r = N, int v = 1) {
	if (r - l == 1) {
		tv[v] = {G[0][l]};
		return;
	}
	int m = (l + r) >> 1;
	build(l, m, v << 1), build(m, r, v<<1|1);
	tv[v].resize(r - l);
	merge(tv[v << 1].begin(), tv[v << 1].end(), tv[v<<1|1].begin(), tv[v<<1|1].end(),
		tv[v].begin());
}

bool get(int L, int R, int x, int y, int l = 0, int r = N, int v = 1) {
	if (L >= r || l >= R) return 0;
	if (L <= l && r <= R) {
		if (tv[v].back() < x) return 0;
		return *lower_bound(tv[v].begin(), tv[v].end(), x) <= y;
	}
	int m = (l + r) >> 1;
	if (get(L, R, x, y, l, m, v << 1)) return 1;
	if (get(L, R, x, y, m, r, v<<1|1)) return 1;
	return 0;
}

vector<int> check_validity(int N_, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> Lq, vector<int> Rq) {
	N = N_;
	M = X.size();
	Q = S.size();
	for (int i = 0 ; i < M ; ++ i) {
		g[X[i]].emplace_back(Y[i]);
		g[Y[i]].emplace_back(X[i]);
	}
	sz = N;
	for (int i = 0 ; i < N ; ++ i) P[i] = i;
	for (int i = 0 ; i < N ; ++ i) {
		for (int j : g[i]) if (j < i) {
			int x = getP(i);
			int y = getP(j);
			if (x != y) {
				P[x] = P[y] = P[sz] = sz;
				go[sz][0] = x, go[sz][1] = y;
				par[x] = par[y] = sz;
				val[sz] = i;
				sz++;
			}
		}
	}
	dfs(sz-1, 0);
	int off = sz;
	for (int i = 0 ; i < N ; ++ i) P[i+off] = i+off;
	sz += N;
	for (int i = N-1 ; i >= 0 ; -- i) {
		for (int j : g[i]) if (j > i) {
			int x = getP(i+off);
			int y = getP(j+off);
			if (x != y) {
				P[x] = P[y] = P[sz] = sz;
				go[sz][0] = x, go[sz][1] = y;
				par[x] = par[y] = sz;
				val[sz] = i;
				sz++;
			}
		}
	}
	dfs(sz-1, 1);
	for (int &i : G[1]) i -= off;
	for (int i : G[0]) cerr << i << " ";
	cerr << ": G[0]\n";
	for (int i : G[1]) cerr << i << " ";
	cerr << ": G[1]\n";
	vector<int>id(N);
	for (int i = 0 ; i < N ; ++ i) {
		id[G[1][i]] = i;
		G[1][i] = i;
	}
	for (int i = 0 ; i < N ; ++ i) {
		G[0][i] = id[G[0][i]];
	}
	for (int i : G[0]) cerr << i << " ";
	cerr << ": G[0]\n";
	for (int i : G[1]) cerr << i << " ";
	cerr << ": G[1]\n";
	build();
	vector<int>ANS(Q);
	for (int q = 0 ; q < Q ; ++ q) {
		int Ls, Rs, Le, Re;
		{
			int v = E[q];
			while (par[v] && val[par[v]] <= Rq[q]) v = par[v];
			Le = L[v], Re = R[v];
		}
		{
			int v = S[q] + off;
			while (par[v] && val[par[v]] >= Lq[q]) v = par[v];
			Ls = L[v], Rs = R[v];
		}
		cerr << Ls << " " << Rs << " " << Le << " " << Re << " LR" << endl;
		bool has = false;
		for (int i = Le ; i <= Re ; ++ i) {
			for (int j = Ls ; j <= Rs ; ++ j) {
				if (G[0][i] == G[1][j]) {
					has = true;
				}
			}
		}
		ANS[q] = get(Le, Re + 1, Ls, Rs);
	}
	return ANS;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:137:8: warning: variable 'has' set but not used [-Wunused-but-set-variable]
  137 |   bool has = false;
      |        ^~~

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