oj.uz

답안 #764351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764351 2023-06-23T10:51:57 Z khshg 늑대인간 (IOI18_werewolf) C++14
34 / 100
 802 ms 524288 KB 
#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, 20>> 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(j, 1, 20) {
		F0R(i, 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 = tl - 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;
		}
	}
	return ans;
}
 
int lst(int valL, int valR, int tl, int tr) {
	int ans = tr + 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;
		}
	}
	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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 802 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 802 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 603 ms 54888 KB Output is correct
2 Correct 694 ms 62828 KB Output is correct
3 Correct 712 ms 62840 KB Output is correct
4 Correct 621 ms 62824 KB Output is correct
5 Correct 607 ms 62784 KB Output is correct
6 Correct 594 ms 62968 KB Output is correct
7 Correct 516 ms 62904 KB Output is correct
8 Correct 558 ms 62912 KB Output is correct
9 Correct 250 ms 62916 KB Output is correct
10 Correct 240 ms 62824 KB Output is correct
11 Correct 288 ms 62916 KB Output is correct
12 Correct 255 ms 62828 KB Output is correct
13 Correct 608 ms 62896 KB Output is correct
14 Correct 592 ms 62844 KB Output is correct
15 Correct 570 ms 62828 KB Output is correct
16 Correct 609 ms 62912 KB Output is correct
17 Correct 517 ms 62836 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 802 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -