oj.uz

답안 #765913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
765913 2023-06-25T07:26:31 Z sentheta 늑대인간 (IOI18_werewolf) C++17
0 / 100
 4000 ms 60648 KB 
#include "werewolf.h"
// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const int N = 2e5+5;
const int LN = 18;

int n, m, q;
V<int> adj[N];

V<int> ans;

int a[N];
struct Stable{
	int mn[N][LN], mx[N][LN];
	void build(){
		rep(i,0,N) mn[i][0] = mx[i][0] = a[i];
		rep(lg,1,LN) for(int i=0; i+(1<<lg)-1<N; i++){
			mn[i][lg] = min(mn[i][lg-1], mn[i+(1<<lg)][lg-1]);
			mx[i][lg] = max(mx[i][lg-1], mx[i+(1<<lg)][lg-1]);
		}
	}
	int qryMin(int l,int r){
		int ret = a[r];
		rep(i,l,r) ret = min(ret, a[l]);
		return ret;

		int lg = __lg(r-l+1);
		return min(mn[l][lg], mn[r-(1<<lg)+1][lg]);
	}
	int qryMax(int l,int r){
		int ret = a[r];
		rep(i,l,r) ret = max(ret, a[l]);
		return ret;

		int lg = __lg(r-l+1);
		return max(mx[l][lg], mx[r-(1<<lg)+1][lg]);
	}
} stable;


int ord[N];
void dfs_ord(int x){
	a[ord[x]] = x;
	for(int y : adj[x]) if(ord[y]==-1){
		ord[y] = ord[x]+1;
		dfs_ord(y);
	}
}

V<int> check_validity(int _n,V<int>_u, V<int>_v,
							V<int>_s, V<int>_e,V<int>_l,V<int>_r){
	n=_n; m=_u.size(); q=_s.size();
	ans = V<int>(q);

	rep(i,0,m){
		adj[_u[i]].push_back(_v[i]);
		adj[_v[i]].push_back(_u[i]);
	}

	rep(i,0,n) ord[i] = -1;
	rep(i,0,n) if(adj[i].size()==1){
		ord[i] = 0;
		dfs_ord(i);
		break;
	}
	assert(ord[0]!=-1);
	stable.build();
	// rep(i,0,n) assert(stable.qryMax(i,i)==a[i]);
	// rep(i,0,n) cout << a[i] << " ";
	// cout << nl;

	rep(i,0,q){
		int s = _s[i], e = _e[i];
		int l = _l[i], r = _r[i];

		int si = ord[s], ei = ord[e];
		// dbg(si); dbg(ei);

		if(si < ei){
			int p = si, q = ei;
			for(int J=1<<LN; J; J/=2){
				if(p+J<=ei && stable.qryMin(si,p+J)>=l) p+=J;
				if(q-J>=si && stable.qryMax(q-J,ei)<=r) q-=J;
			}
			// dbg(p); dbg(q);
			ans[i] = q<=p;
		}

		if(ei < si){
			int p = ei, q = si;
			for(int J=1<<LN; J; J/=2){
				if(p+J<=si && stable.qryMax(ei,p+J)<=r) p+=J;
				if(q-J>=ei && stable.qryMin(q-J,si)>=l) q-=J;
			}
			ans[i] = q<=p;
		}
	}

	return ans;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 33108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 33108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4033 ms 60648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 33108 KB Output isn't correct
2 Halted 0 ms 0 KB -