oj.uz

Submission #765922

# Submission time Handle Problem Language Result Execution time Memory
765922 2023-06-25T07:36:52 Z sentheta Werewolf (IOI18_werewolf) C++17
34 / 100
 490 ms 69860 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-1))][lg-1]);
			mx[i][lg] = max(mx[i][lg-1], mx[i+(1<<(lg-1))][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){
		ord[i] = 0;
		dfs_ord(i);
		break;
	}
	stable.build();
	// 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

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

Subtask #2
0 / 8.0

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

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 61360 KB Output is correct
2 Correct 365 ms 69708 KB Output is correct
3 Correct 377 ms 69708 KB Output is correct
4 Correct 407 ms 69860 KB Output is correct
5 Correct 446 ms 69708 KB Output is correct
6 Correct 490 ms 69768 KB Output is correct
7 Correct 402 ms 69772 KB Output is correct
8 Correct 311 ms 69720 KB Output is correct
9 Correct 210 ms 69724 KB Output is correct
10 Correct 228 ms 69748 KB Output is correct
11 Correct 233 ms 69724 KB Output is correct
12 Correct 233 ms 69780 KB Output is correct
13 Correct 381 ms 69724 KB Output is correct
14 Correct 395 ms 69768 KB Output is correct
15 Correct 401 ms 69708 KB Output is correct
16 Correct 404 ms 69780 KB Output is correct
17 Correct 380 ms 69784 KB Output is correct

Subtask #4
0 / 51.0

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