oj.uz

Submission #314597

# Submission time Handle Problem Language Result Execution time Memory
314597 2020-10-20T12:20:41 Z tengiz05 Werewolf (IOI18_werewolf) C++17
49 / 100
 788 ms 37192 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<int> g1(n);
			vector<int> g2(n);
			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 4992 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 5 ms 5120 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4992 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 4992 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 5 ms 5120 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 309 ms 5580 KB Output is correct
11 Correct 197 ms 5624 KB Output is correct
12 Correct 36 ms 5376 KB Output is correct
13 Correct 340 ms 5496 KB Output is correct
14 Correct 233 ms 5496 KB Output is correct
15 Correct 263 ms 5504 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 37104 KB Output is correct
2 Correct 707 ms 37104 KB Output is correct
3 Correct 737 ms 37028 KB Output is correct
4 Correct 779 ms 37116 KB Output is correct
5 Correct 767 ms 37040 KB Output is correct
6 Correct 765 ms 37036 KB Output is correct
7 Correct 754 ms 37104 KB Output is correct
8 Correct 674 ms 36976 KB Output is correct
9 Correct 614 ms 36980 KB Output is correct
10 Correct 614 ms 37104 KB Output is correct
11 Correct 629 ms 36976 KB Output is correct
12 Correct 620 ms 36980 KB Output is correct
13 Correct 720 ms 37032 KB Output is correct
14 Correct 735 ms 37184 KB Output is correct
15 Correct 723 ms 37192 KB Output is correct
16 Correct 712 ms 36976 KB Output is correct
17 Correct 759 ms 36976 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 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 5 ms 5120 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 309 ms 5580 KB Output is correct
11 Correct 197 ms 5624 KB Output is correct
12 Correct 36 ms 5376 KB Output is correct
13 Correct 340 ms 5496 KB Output is correct
14 Correct 233 ms 5496 KB Output is correct
15 Correct 263 ms 5504 KB Output is correct
16 Correct 788 ms 37104 KB Output is correct
17 Correct 707 ms 37104 KB Output is correct
18 Correct 737 ms 37028 KB Output is correct
19 Correct 779 ms 37116 KB Output is correct
20 Correct 767 ms 37040 KB Output is correct
21 Correct 765 ms 37036 KB Output is correct
22 Correct 754 ms 37104 KB Output is correct
23 Correct 674 ms 36976 KB Output is correct
24 Correct 614 ms 36980 KB Output is correct
25 Correct 614 ms 37104 KB Output is correct
26 Correct 629 ms 36976 KB Output is correct
27 Correct 620 ms 36980 KB Output is correct
28 Correct 720 ms 37032 KB Output is correct
29 Correct 735 ms 37184 KB Output is correct
30 Correct 723 ms 37192 KB Output is correct
31 Correct 712 ms 36976 KB Output is correct
32 Correct 759 ms 36976 KB Output is correct
33 Incorrect 730 ms 30480 KB Output isn't correct
34 Halted 0 ms 0 KB -