| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 764328 | khshg | Werewolf (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 0;// __lg(R - L + 1); // !!!!!!!!!!!!!!!!!!!
return min(mn[L][lenlg], mn[R - (1 << lenlg) + 1][lenlg]);
}
int range_mx(int L, int R) {
int lenlg = 0;//__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 = tr;
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;
}
}
return ans;
}
int lst(int valL, int valR, int tl, int tr) {
int ans = tl;
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;
}
}
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;
}