oj.uz

Submission #314598

# Submission time Handle Problem Language Result Execution time Memory
314598 2020-10-20T12:26:39 Z tengiz05 Werewolf (IOI18_werewolf) C++17
49 / 100
 793 ms 37104 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5, inf = 1e9;
int n, sz, m, timer=0;
int depth[N];
int a[N];
vector<int> edges[N];
void dfs(int u, int p, int d = 0){
	a[u]=timer,timer++;
	depth[u] = d;
	for(auto v : edges[u]){
		if(v == p)continue;
		dfs(v, u, d+1);
	}
}
struct segtree {
	struct Node{
		int mn, mx;
	};
	vector<Node> t;
	Node neutral = {inf, 0};
	void build(){
		sz=1;
		while(sz<n)sz<<=1;
		t.assign(sz*2, neutral);
		for(int i=0;i<n;i++){
			t[a[i]+sz] = {i, i};
		}for(int i=sz-1;i>0;i--){
			t[i] = {min(t[i*2].mn, t[i*2+1].mn), max(t[i*2].mx, t[i*2+1].mx)};
		}
	}
	int f_less(int l, int r, int L, int R, int node, int x){
		if(L >= r || R <= l)return inf;
		if(R-L == 1){
			if(L >= l && t[node].mn < x)return L;
			else return inf;
		}int mid = (L+R)/2;
		if(L >= l && R <= r){
			if(t[node*2].mn < x)return f_less(l, r, L, mid, node*2, x);
			else return f_less(l, r, mid, R, node*2+1, x);
		}return min(f_less(l, r, L, mid, node*2, x), 
		            f_less(l, r, mid, R, node*2+1, x));
	}int f_less(int l, int x){return f_less(l, sz, 0, sz, 1, x);}
	
	int f_great(int l, int r, int L, int R, int node, int x){
		if(L >= r || R <= l)return inf;
		if(R-L == 1){
			if(L >= l && t[node].mx > x)return L;
			else return inf;
		}int mid = (L+R)/2;
		if(L >= l && R <= r){
			if(t[node*2].mx > x)return f_great(l, r, L, mid, node*2, x);
			else return f_great(l, r, mid, R, node*2+1, x);
		}return min(f_great(l, r, L, mid, node*2, x),
		            f_great(l, r, mid, R, node*2+1, x));
	}int f_great(int l, int x){return f_great(l, sz, 0, sz, 1, x);}
		
//903475834u1ify98pw75ruehruiae7893yu524hfuiayw78ryhweajkrasfasfasdfsddasf4589i7889he6ghwerg	
	int l_less(int l, int r, int L, int R, int node, int x){
		if(L >= r || R <= l)return -1;
		if(R-L == 1){
			if(R <= r && t[node].mn < x)return L;
			else return -1;
		}int mid = (L+R)/2;
		if(L >= l && R <= r){
			if(t[node*2+1].mn < x)return l_less(l, r, mid, R, node*2+1, x);
			else return l_less(l, r, L, mid, node*2, x);
		}return max(l_less(l, r, L, mid, node*2, x), 
		            l_less(l, r, mid, R, node*2+1, x));
	}int l_less(int r, int x){return l_less(0, r, 0, sz, 1, x);}
	
	int l_great(int l, int r, int L, int R, int node, int x){
		if(L >= r || R <= l)return -1;
		if(R-L == 1){
			if(R <= r && t[node].mx > x)return L;
			else return -1;
		}int mid = (L+R)/2;
		if(L >= l && R <= r){
			if(t[node*2+1].mx > x)return l_great(l, r, mid, R, node*2+1, x);
			else return l_great(l, r, L, mid, node*2, x);
		}return max(l_great(l, r, L, mid, node*2, x),
		            l_great(l, r, mid, R, node*2+1, x));
	}int l_great(int r, int x){return l_great(0, r, 0, sz, 1, x);}
}seg;
// =================================================================
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	n = N;
	m = X.size();
	for(int i=0;i<m;i++){
		edges[X[i]].push_back(Y[i]);
		edges[Y[i]].push_back(X[i]);
	}
	int Q = S.size();
	if(n <= 3000 && m <= 6000 && Q <= 3000){
		vector<int> ans;
		for(int i=0;i<Q;i++){
			vector<bool> used1(n);
			vector<bool> used2(n);
			int ans1=0;
			int l=L[i], r=R[i];
			queue<int> q;
			q.push(S[i]);used1[S[i]]=true;
			while(!q.empty()){
				int u = q.front();q.pop();
				for(auto v : edges[u]){
					if(!used1[v]&&v >= l){
						q.push(v);
						used1[v]=true;
					}
				}
			}
			q.push(E[i]);used2[E[i]]=true;
			while(!q.empty()){
				int u = q.front();q.pop();
				for(auto v : edges[u]){
					if(!used2[v]&&v <= r){
						q.push(v);
						used2[v]=true;
					}
				}
			}for(int u=0;u<n;u++)ans1 |= (used1[u]&&used2[u]);
			ans.push_back(ans1);
		}return ans;
	}
	dfs(0, 0);
	int mxdep = 0, inddep = 0;
	for(int i=0;i<n;i++){
		if(depth[i] > mxdep)mxdep=depth[i], inddep = i;
	}timer=0;
	dfs(inddep, inddep);
	seg.build();
	vector<int> ans;
	for(int i=0;i<Q;i++){
		int start = a[S[i]], end = a[E[i]];
		int l = L[i], r = R[i];
		int ans1 = 1;
		if(start <= end){
			int ff = seg.f_less(start, l)-1;
			int ss = seg.l_great(end, r)+1;
			if(ff < ss)ans1 = 0;
		}else {
			int ff = seg.l_less(start, l)+1;
			int ss = seg.f_great(end, r)-1;
			if(ff > ss)ans1 = 0;
		}
		ans.push_back(ans1);
	}return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4864 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4864 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 295 ms 5248 KB Output is correct
11 Correct 184 ms 5316 KB Output is correct
12 Correct 27 ms 5248 KB Output is correct
13 Correct 325 ms 5248 KB Output is correct
14 Correct 224 ms 5248 KB Output is correct
15 Correct 250 ms 5628 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 36952 KB Output is correct
2 Correct 704 ms 37020 KB Output is correct
3 Correct 728 ms 36976 KB Output is correct
4 Correct 739 ms 36976 KB Output is correct
5 Correct 738 ms 37012 KB Output is correct
6 Correct 777 ms 36976 KB Output is correct
7 Correct 773 ms 36976 KB Output is correct
8 Correct 678 ms 36980 KB Output is correct
9 Correct 580 ms 36976 KB Output is correct
10 Correct 615 ms 36976 KB Output is correct
11 Correct 643 ms 36976 KB Output is correct
12 Correct 616 ms 36976 KB Output is correct
13 Correct 714 ms 37004 KB Output is correct
14 Correct 719 ms 37032 KB Output is correct
15 Correct 716 ms 36976 KB Output is correct
16 Correct 706 ms 37104 KB Output is correct
17 Correct 768 ms 36976 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4864 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 295 ms 5248 KB Output is correct
11 Correct 184 ms 5316 KB Output is correct
12 Correct 27 ms 5248 KB Output is correct
13 Correct 325 ms 5248 KB Output is correct
14 Correct 224 ms 5248 KB Output is correct
15 Correct 250 ms 5628 KB Output is correct
16 Correct 793 ms 36952 KB Output is correct
17 Correct 704 ms 37020 KB Output is correct
18 Correct 728 ms 36976 KB Output is correct
19 Correct 739 ms 36976 KB Output is correct
20 Correct 738 ms 37012 KB Output is correct
21 Correct 777 ms 36976 KB Output is correct
22 Correct 773 ms 36976 KB Output is correct
23 Correct 678 ms 36980 KB Output is correct
24 Correct 580 ms 36976 KB Output is correct
25 Correct 615 ms 36976 KB Output is correct
26 Correct 643 ms 36976 KB Output is correct
27 Correct 616 ms 36976 KB Output is correct
28 Correct 714 ms 37004 KB Output is correct
29 Correct 719 ms 37032 KB Output is correct
30 Correct 716 ms 36976 KB Output is correct
31 Correct 706 ms 37104 KB Output is correct
32 Correct 768 ms 36976 KB Output is correct
33 Incorrect 737 ms 27760 KB Output isn't correct
34 Halted 0 ms 0 KB -