oj.uz

Submission #767263

# Submission time Handle Problem Language Result Execution time Memory
767263 2023-06-26T14:50:51 Z amunduzbaev Werewolf (IOI18_werewolf) C++17
15 / 100
 271 ms 38668 KB 
#include "werewolf.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef int64_t ll;
typedef int32_t ii;
//~ #define int ll

struct ST{
	//~ vector<int> Min, Max;
	vector<int> a;
	int N;
	
	ST(int N): N(N){
		//~ Min.resize(N << 2);
		//~ Max.resize(N << 2);
		a.resize(N);
	}
	
	void set(int i, int v){
		a[i] = v;
	}
	
	int first_less(int l, int r, int v){
		for(int i=l;i<=r;i++){
			if(a[i] < v) return i;
		}
		return -1;
	}
	int last_less(int l, int r, int v){
		for(int i=r;i>=l;i--){
			if(a[i] < v) return i;
		}
		return -1;
	}
	int first_big(int l, int r, int v){
		for(int i=l;i<=r;i++){
			if(a[i] > v) return i;
		}
		return -1;
	}
	int last_big(int l, int r, int v){
		for(int i=r;i>=l;i--){
			if(a[i] > v) return i;
		}
		return -1;
	}
	
	//~ void set(int i, int v, int lx, int rx, int x){
		//~ if(lx == rx) { Min[x] = Max[x] = v; return; }
		//~ int m = (lx + rx) >> 1;
		//~ if(i <= m) set(i, v, lx, m, x << 1);
		//~ else set(i, v, m + 1, rx, x << 1 | 1);
		//~ Min[x] = min(Min[x << 1], Min[x << 1 | 1]);
		//~ Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
	//~ }
	
	//~ void set(int i, int v){
		//~ set(i, v, 0, N, 1);
	//~ }
	
	//~ int first_less(int l, int r, int v, int lx, int rx, int x){
		//~ if(lx > r || rx < l) return -1;
		//~ if(lx >= l && rx <= r){
			//~ if(Min[x] >= v) return -1;
			//~ if(lx == rx) return lx;
			//~ int m = (lx + rx) >> 1;
			//~ if(Min[x << 1] < v) return first_less(l, r, v, lx, m, x << 1);
			//~ else return first_less(l, r, v, m + 1, rx, x << 1 | 1);
		//~ }
		//~ int m = (lx + rx) >> 1;
		//~ int res = first_less(l, r, v, lx, m, x << 1);
		//~ if(res == -1) res = first_less(l, r, v, m + 1, rx, x << 1 | 1);
		//~ return res;
	//~ }
	
	//~ int first_less(int l, int r, int v){
		//~ return first_less(l, r, v, 0, N, 1);
	//~ }
	
	//~ int last_less(int l, int r, int v, int lx, int rx, int x){
		//~ if(lx > r || rx < l) return -1;
		//~ if(lx >= l && rx <= r){
			//~ if(Min[x] >= v) return -1;
			//~ if(lx == rx) return lx;
			//~ int m = (lx + rx) >> 1;
			//~ if(Min[x << 1 | 1] < v) return last_less(l, r, v, m + 1, rx, x << 1 | 1);
			//~ else return last_less(l, r, v, lx, m, x << 1);
		//~ }
		//~ int m = (lx + rx) >> 1;
		//~ int res = last_less(l, r, v, m + 1, rx, x << 1 | 1);
		//~ if(res == -1) res = last_less(l, r, v, lx, m, x << 1);
		//~ return res;
	//~ }
	
	//~ int last_less(int l, int r, int v){
		//~ return last_less(l, r, v, 0, N, 1);
	//~ }
	
	//~ int first_big(int l, int r, int v, int lx, int rx, int x){
		//~ if(lx > r || rx < l) return -1;
		//~ if(lx >= l && rx <= r){
			//~ if(Max[x] <= v) return -1;
			//~ if(lx == rx) return lx;
			//~ int m = (lx + rx) >> 1;
			//~ if(Max[x << 1] > v) return first_big(l, r, v, lx, m, x << 1);
			//~ else return first_big(l, r, v, m + 1, rx, x << 1 | 1);
		//~ }
		//~ int m = (lx + rx) >> 1;
		//~ int res = first_big(l, r, v, lx, m, x << 1);
		//~ if(res == -1) res = first_big(l, r, v, m + 1, rx, x << 1 | 1);
		//~ return res;
	//~ }
	
	//~ int first_big(int l, int r, int v){
		//~ return first_big(l, r, v, 0, N, 1);
	//~ }
	
	//~ int last_big(int l, int r, int v, int lx, int rx, int x){
		//~ if(lx > r || rx < l) return -1;
		//~ if(lx >= l && rx <= r){
			//~ if(Max[x] <= v) return -1;
			//~ if(lx == rx) return lx;
			//~ int m = (lx + rx) >> 1;
			//~ if(Max[x << 1 | 1] > v) return last_big(l, r, v, m + 1, rx, x << 1 | 1);
			//~ else return last_big(l, r, v, lx, m, x << 1);
		//~ }
		//~ int m = (lx + rx) >> 1;
		//~ int res = last_big(l, r, v, m + 1, rx, x << 1 | 1);
		//~ if(res == -1) res = last_big(l, r, v, lx, m, x << 1);
		//~ return res;
	//~ }
	
	//~ int last_big(int l, int r, int v){
		//~ return last_big(l, r, v, 0, N, 1);
	//~ }
};

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
	int m = x.size();
	int q = s.size();
	vector<vector<int>> edges(n);
	for(int i=0;i<m;i++){
		edges[x[i]].push_back(y[i]);
		edges[y[i]].push_back(x[i]);
	}
	
	if(n <= 3000 && m <= 6000 && q <= 3000){
		vector<int> used_s(n), used_e(n);
		function<void(vector<int>&, int, int, int)> dfs = [&](vector<int>& used, int u, int l, int r){
			used[u] = 1;
			for(auto x : edges[u]){
				if(!used[x] && l <= x && x <= r){
					dfs(used, x, l, r);
				}
			}
		};
		
		vector<int> ans(q);
		for(int i=0;i<q;i++){
			fill(used_s.begin(), used_s.end(), 0);
			fill(used_e.begin(), used_e.end(), 0);
			dfs(used_s, s[i], l[i], n);
			dfs(used_e, e[i], 0, r[i]);
			
			//~ for(int j=0;j<n;j++){
				//~ cout<<used_s[j]<<" ";
			//~ } cout<<"\n";
			//~ for(int j=0;j<n;j++){
				//~ cout<<used_e[j]<<" ";
			//~ } cout<<"\n";
			
			for(int j=0;j<n;j++){
				if(used_s[j] && used_e[j]){
					ans[i] = 1;
					break;
				}
			}
		}
		
		return ans;
	}
	
	ST tree(n);
	
	int root = 0;
	for(int i=0;i<n;i++){
		if((int)edges[i].size() == 1){
			root = i;
			break;
		}
	}
	
	vector<int> pos(n);
	int last = 0;
	
	function<void(int, int)> dfs = [&](int u, int p){
		pos[u] = last++;
		for(auto x : edges[u]){
			if(x == p) continue;
			dfs(x, u);
		}
	};
	dfs(root, root);
	
	for(int i=0;i<n;i++){
		tree.set(pos[i], i);
	}
	
	vector<int> ans(q);
	
	for(int j=0;j<q;j++){
		int l_= pos[s[j]], r_ = pos[e[j]];
		if(l_ < r_){
			int R = tree.last_big(l_, r_, r[j]);
			int L = tree.first_less(l_, r_, l[j]);
			if(L == -1 || R == -1 || L + 1 < R){
				ans[j] = 1;
			}
		} else {
			int L = tree.first_big(r_, l_, r[j]);
			int R = tree.last_less(r_, l_, l[j]);
			if(L == -1 || R == -1 || L + 1 < R){
				ans[j] = 1;
			}
		}
	}
	
	return ans;
}

/*

6 6 3
5 1
1 2
1 3
3 4
3 0
2 5
4 2 1 2
4 2 2 2
5 4 3 4

5 4 4
4 1
1 0
0 3
3 2
4 0 1 1 
4 3 1 3
2 0 1 1
3 1 2 2

*/

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 237 ms 696 KB Output is correct
11 Correct 119 ms 596 KB Output is correct
12 Correct 19 ms 948 KB Output is correct
13 Correct 271 ms 704 KB Output is correct
14 Correct 168 ms 628 KB Output is correct
15 Correct 249 ms 884 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 237 ms 696 KB Output is correct
11 Correct 119 ms 596 KB Output is correct
12 Correct 19 ms 948 KB Output is correct
13 Correct 271 ms 704 KB Output is correct
14 Correct 168 ms 628 KB Output is correct
15 Correct 249 ms 884 KB Output is correct
16 Incorrect 189 ms 38668 KB Output isn't correct
17 Halted 0 ms 0 KB -