oj.uz

Submission #767293

# Submission time Handle Problem Language Result Execution time Memory
767293 2023-06-26T15:08:31 Z amunduzbaev Werewolf (IOI18_werewolf) C++17
34 / 100
 319 ms 524288 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;
	//~ }
	//~ int get(int l, int r){
		//~ int res = 0;
		//~ for(int i=l;i<=r;i++) res = max(res, a[i]);
		//~ return res;
	//~ }
	
	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 get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return Max[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int get(int l, int r){
		return get(l, r, 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++){
				//~ if(used_s[j] && used_e[j]){
					//~ ans[i] = 1;
					//~ break;
				//~ }
			//~ }
		//~ }
		
		//~ return ans;
	//~ }
	
	ST tree(n);
	
	int root = -1;
	for(int i=0;i<n;i++){
		if((int)edges[i].size() == 1){
			root = i;
			break;
		}
	}
	
	assert(~root);
	
	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);
	
	vector<int> a(n);
	for(int i=0;i<n;i++){
		a[pos[i]] = 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 p = tree.first_less(l_, r_, l[j]);
			//~ if(L == -1 || R == -1 || L + 1 < R){
				//~ ans[j] = 1;
			//~ }
			int p = tree.first_less(l_, r_, l[j]);
			assert(p == -1 || l_ < p);
			if(p == -1 || (l[j] <= a[p - 1] && a[p - 1] <= r[j] && tree.get(p, r_) <= r[j])){
				ans[j] = 1;
			}
		} else {
			//~ int L = tree.first_big(r_, l_, r[j]);
			//~ int p = tree.last_less(r_, l_, l[j]);
			//~ if(L == -1 || R == -1 || L + 1 < R){
				//~ ans[j] = 1;
			//~ }
			int p = tree.last_less(r_, l_, l[j]);
			assert(p == -1 || p < l_);
			if(p == -1 || (l[j] <= a[p + 1] && a[p + 1] <= r[j] && tree.get(r_, p) <= r[j])){
				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 3 3

*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 216 ms 524288 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 216 ms 524288 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 319 ms 44948 KB Output is correct
2 Correct 283 ms 53356 KB Output is correct
3 Correct 266 ms 53240 KB Output is correct
4 Correct 287 ms 53252 KB Output is correct
5 Correct 294 ms 53348 KB Output is correct
6 Correct 288 ms 53364 KB Output is correct
7 Correct 294 ms 53356 KB Output is correct
8 Correct 248 ms 53360 KB Output is correct
9 Correct 232 ms 53328 KB Output is correct
10 Correct 242 ms 53244 KB Output is correct
11 Correct 242 ms 53236 KB Output is correct
12 Correct 241 ms 53324 KB Output is correct
13 Correct 280 ms 53236 KB Output is correct
14 Correct 281 ms 53372 KB Output is correct
15 Correct 269 ms 53252 KB Output is correct
16 Correct 288 ms 53364 KB Output is correct
17 Correct 297 ms 53324 KB Output is correct

Subtask #4
0 / 51.0

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