oj.uz

Submission #817394

# Submission time Handle Problem Language Result Execution time Memory
817394 2023-08-09T12:12:38 Z Dan4Life Werewolf (IOI18_werewolf) C++17
34 / 100
 2151 ms 524292 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
using vi = vector<int>;
const int mxN = (int)2e5+10;
int n, m, q;
vi adj[mxN], a;
int pos[mxN], mnSeg[mxN*2], mxSeg[mxN*2];

void upd(int x, int v, int seg[], bool t, int p=0, int l=0, int r=n-1){
	if(l==r){ seg[p] = v; return; }
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	if(x<=mid) upd(x,v,seg,t,p+1,l,mid);
	else upd(x,v,seg,t,rp,mid+1,r);
	if(t) seg[p] = max(seg[p+1],seg[rp]);
	else seg[p] = min(seg[p+1],seg[rp]);
}
 
int rmq(int i, int j, int seg[], bool t, int p=0, int l=0, int r=n-1){
	if(i>r or j<l or i>j) return t?0:mxN;
	if(i<=l and r<=j) return seg[p];
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	int le = t?0:mxN; int ri = le;
	if(i<=mid) le = rmq(i,j,seg,t,p+1,l,mid);
	if(j>mid) ri = rmq(i,j,seg,t,rp,mid+1,r);
	if(t) return max(le,ri);
	return min(le,ri);
}

void dfs(int s, int p){
	a.pb(s);
	for(auto u : adj[s])
		if(u!=p) dfs(u,s);
}

vi check_validity(int N, vi U, vi V, vi S, vi T, vi L, vi R) {
	n = N, m = sz(U), q = sz(S); vi ans(q, 0);
	for(int i = 0; i < m; i++){
		int a = U[i], b = V[i];
		adj[a].pb(b); adj[b].pb(a);
	}
	for(int i = 0; i < n; i++){
		if(sz(adj[i])==1){
			dfs(i,-1); break;
		}
	}
	for(int i = 0; i < n; i++) 
		upd(i,a[i],mnSeg,0), upd(i,a[i],mxSeg,1),pos[a[i]]=i;
	for(int i = 0; i < q; i++){
		int s = pos[S[i]], t = pos[T[i]];
		if(s<t){
			int l = s, r = t;
			while(l<r){
				int mid = (l+r+1)/2;
				if(rmq(s,mid,mnSeg,0)>=L[i]) l=mid;
				else r=mid-1;
			}
			int x = l;
			l = s, r = t;
			while(l<r){
				int mid = (l+r)/2;
				if(rmq(mid,t,mxSeg,1)<=R[i]) r=mid;
				else l=mid+1;
			}
			ans[i] = x>=l;
		}
		else{
			swap(s,t);
			int l = s, r = t;
			while(l<r){
				int mid = (l+r+1)/2;
				if(rmq(s,mid,mxSeg,1)<=R[i]) l=mid;
				else r=mid-1;
			}
			int x = l;
			l = s, r = t;
			while(l<r){
				int mid = (l+r)/2;
				if(rmq(mid,t,mnSeg,0)>=L[i]) r=mid;
				else l=mid+1;
			}
			ans[i] = x>=l;
		}
	}
	return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 479 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 479 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1659 ms 39016 KB Output is correct
2 Correct 2033 ms 44088 KB Output is correct
3 Correct 2009 ms 44088 KB Output is correct
4 Correct 1918 ms 44092 KB Output is correct
5 Correct 1942 ms 44092 KB Output is correct
6 Correct 1766 ms 44080 KB Output is correct
7 Correct 1974 ms 44084 KB Output is correct
8 Correct 2005 ms 44088 KB Output is correct
9 Correct 901 ms 44096 KB Output is correct
10 Correct 1102 ms 44076 KB Output is correct
11 Correct 1275 ms 44068 KB Output is correct
12 Correct 1557 ms 44096 KB Output is correct
13 Correct 2151 ms 44088 KB Output is correct
14 Correct 1967 ms 44088 KB Output is correct
15 Correct 2011 ms 44088 KB Output is correct
16 Correct 2105 ms 44092 KB Output is correct
17 Correct 2041 ms 44088 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 479 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -