Submission #764319

#	Time	Username	Problem	Language	Result	Execution time	Memory
764319		khshg	Werewolf (IOI18_werewolf)	C++14	0 / 100	877 ms	524288 KiB

werewolf

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

using ll = long long;
using ld = long double;
using str = string;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
#define mp make_pair
#define ff first
#define ss second

#define ar array
template<class T> using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<ld>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;

#define sz(x) (int)((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define trav(a, x) for(auto& a : x)

template<class T> bool ckmin(T& a, const T& b) { return (b < a ? a = b, 1 : 0); }
template<class T> bool ckmax(T& a, const T& b) { return (b > a ? a = b, 1 : 0); }

V<vi> adj;

vi root(int s) {
	vb vis(sz(adj));
	vi res;
	queue<pi> q; q.push({s, -1});
	while(sz(q)) {
		pi cur = q.ft; q.pop();
		res.pb(cur.ff);
		trav(u, adj[cur.ff]) {
			if(cur.ss != u) {
				q.push({u, cur.ff});
			}
		}
	}
	return res;
}

V<ar<int, 24>> mx, mn;
void build(vi A) {
	int N = sz(A);
	mx.rsz(N); mn.rsz(N);
	F0R(i, N) {
		mx[i][0] = mn[i][0] = A[i];
	}
	FOR(i, 1, 24) {
		F0R(j, N) {
			mx[i][j] = max(mx[i][j - 1], mx[min(N - 1, i + (1 << (j - 1)))][j - 1]);
			mn[i][j] = min(mn[i][j - 1], mn[min(N - 1, i + (1 << (j - 1)))][j - 1]);
		}
	}
}

int range_mn(int L, int R) {
	int lenlg = __lg(R - L + 1); // !!!!!!!!!!!!!!!!!!!
	return min(mn[L][lenlg], mn[R - (1 << lenlg) + 1][lenlg]);
}

int range_mx(int L, int R) {
	int lenlg = __lg(R - L + 1); // !!!!!!!!!!!!!!!!!!!
	return max(mx[L][lenlg], mx[R - (1 << lenlg) + 1][lenlg]);
}

int rst(int valL, int valR, int tl, int tr) {
	int ans = -1;
	while(tl <= tr) {
		int mid = (tl + tr) / 2;
		if((valL <= range_mn(mid, tr) && range_mn(mid, tr) <= valR) || (valL <= range_mx(mid, tr) && range_mx(mid, tr) <= valR)) {
			ans = mid;
			tl = mid + 1;
		} else {
			tr = mid - 1;
		}
	}
	assert(ans != -1);
	return ans;
}

int lst(int valL, int valR, int tl, int tr) {
	int ans = -1;
	while(tl <= tr) {
		int mid = (tl + tr) / 2;
		if((valL <= range_mn(tl, mid) && range_mn(tl, mid) <= valR) || (valL <= range_mx(tl, mid) && range_mx(tl, mid) <= valR)) {
			ans = mid;
			tr = mid - 1;
		} else {
			tl = mid + 1;
		}
	}
	assert(ans != -1);
	return ans;
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	adj.rsz(N);
	int M = sz(X), Q = sz(S);
	F0R(i, M) {
		adj[X[i]].eb(Y[i]);
		adj[Y[i]].eb(X[i]);
	}
	vi flat, pos(N);
	F0R(i, N) {
		if(sz(adj[i]) == 1) {
			flat = root(i);
			break;
		}
	}
	F0R(i, N) {
		pos[flat[i]] = i;
	}
	build(flat);
	vi ans(Q);
	F0R(query, Q) {
		if(pos[E[query]] < pos[S[query]]) {
			int W = rst(min(0, L[query] - 1), L[query] - 1, pos[E[query]], pos[S[query]]);
			int H = lst(R[query] + 1, max(N - 1, R[query] + 1), pos[E[query]], pos[S[query]]);
			ans[query] = (W + 1 < H);
		} else {
			int H = rst(R[query] + 1, max(N - 1, R[query] + 1), pos[S[query]], pos[E[query]]);
			int W = lst(min(0, L[query] - 1), L[query] - 1, pos[S[query]], pos[E[query]]);
			ans[query] = (W > H + 1);
		}
	}
	return ans;
}

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