oj.uz

Submission #768755

# Submission time Handle Problem Language Result Execution time Memory
768755 2023-06-28T14:36:01 Z Baytoro Werewolf (IOI18_werewolf) C++17
34 / 100
 537 ms 73820 KB 
#include "werewolf.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2e5+5;
vector<int> g[N];
int v[N],used[N],a[N];
void dfs(int x){
	a[v[x]]=x;
	for(auto it: g[x]){
		if(v[it]!=-1) continue;
		v[it]=v[x]+1;
		dfs(it);
	}
}
struct SparseTable{
	int mn[N][21],mx[N][21];
	void build(){
		for(int i=0;i<N;i++)
			mn[i][0]=mx[i][0]=a[i];
		for(int j=1;j<21;j++){
			for(int i=0;i+(1<<j)-1<N;i++){
				mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
				mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
			}
		}
	}
	int minn(int l, int r){
		int lg=__lg(r-l+1);
		return min(mn[l][lg],mn[r-(1<<lg)+1][lg]);
	}
	int maxx(int l, int r){
		int lg=__lg(r-l+1);
		return max(mx[l][lg],mx[r-(1<<lg)+1][lg]);
	}
} sparse;
vector<int> check_validity(int n, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R){
	for(int i=0;i<N;i++) v[i]=-1;
	int m=X.size(),q=S.size();
	//Subtask 3
	for(int i=0;i<m;i++){
		g[X[i]].pb(Y[i]);
		g[Y[i]].pb(X[i]);
	}
	for(int i=0;i<n;i++){
		if(g[i].size()==1){
			v[i]=0;
			dfs(i);
			break;
		}
	}
	sparse.build();
	vector<int> ans(q);
	for(int i=0;i<q;i++){
		int l=v[S[i]],r=v[E[i]];
		if(l<r){
			//cout<<1<<endl;
			int lx=l,rx=r;
			for(int j=(1<<20);j>0;j/=2){
				if(lx+j<=r && sparse.minn(l,lx+j)>=L[i]) 
					lx+=j;
				if(rx-j>=l && sparse.maxx(rx-j,r)<=R[i])
					rx-=j;
			}
			if(rx<=lx) ans[i]=1;
		}
		if(r<l){
			//cout<<2<<endl;
			int lx=r, rx=l;
			for(int j=(1<<20);j>0;j/=2){
				if(lx+j<=l && sparse.maxx(r,lx+j)<=R[i]) 
					lx+=j;
				if(rx-j>=r && sparse.minn(rx-j,l)>=L[i])
					rx-=j;
			}
			if(rx<=lx) ans[i]=1;
		}
	}
	return ans;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 38612 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 537 ms 66520 KB Output is correct
2 Correct 415 ms 72208 KB Output is correct
3 Correct 404 ms 73688 KB Output is correct
4 Correct 439 ms 73704 KB Output is correct
5 Correct 454 ms 73704 KB Output is correct
6 Correct 487 ms 73696 KB Output is correct
7 Correct 435 ms 73716 KB Output is correct
8 Correct 319 ms 73688 KB Output is correct
9 Correct 213 ms 73672 KB Output is correct
10 Correct 214 ms 73576 KB Output is correct
11 Correct 224 ms 73572 KB Output is correct
12 Correct 237 ms 73688 KB Output is correct
13 Correct 396 ms 73684 KB Output is correct
14 Correct 414 ms 73676 KB Output is correct
15 Correct 406 ms 73804 KB Output is correct
16 Correct 405 ms 73700 KB Output is correct
17 Correct 416 ms 73820 KB Output is correct

Subtask #4
0 / 51.0

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