oj.uz

Submission #765885

# Submission time Handle Problem Language Result Execution time Memory
765885 2023-06-25T06:58:42 Z sentheta Werewolf (IOI18_werewolf) C++17
0 / 100
 491 ms 61360 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 lg = __lg(r-l+1);
		return min(mn[l][lg], mn[r-(1<<lg)+1][lg]);
	}
	int qryMax(int l,int r){
		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){
		dfs_ord(i);
		break;
	}
	stable.build();

	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];

		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;
			}
			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

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 33108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 33108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 491 ms 61360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 33108 KB Output isn't correct
2 Halted 0 ms 0 KB -