oj.uz

Submission #767295

# Submission time Handle Problem Language Result Execution time Memory
767295 2023-06-26T15:09:13 Z amunduzbaev Werewolf (IOI18_werewolf) C++17
49 / 100
 294 ms 44956 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;
	int N;
	
	ST(int N): N(N){
		Min.resize(N << 2);
		Max.resize(N << 2);
	}
	
	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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 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 2 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 1 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 228 ms 692 KB Output is correct
11 Correct 117 ms 620 KB Output is correct
12 Correct 19 ms 948 KB Output is correct
13 Correct 256 ms 704 KB Output is correct
14 Correct 159 ms 628 KB Output is correct
15 Correct 255 ms 876 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 44944 KB Output is correct
2 Correct 294 ms 44956 KB Output is correct
3 Correct 258 ms 44952 KB Output is correct
4 Correct 273 ms 44952 KB Output is correct
5 Correct 264 ms 44836 KB Output is correct
6 Correct 269 ms 44956 KB Output is correct
7 Correct 269 ms 44936 KB Output is correct
8 Correct 252 ms 44952 KB Output is correct
9 Correct 209 ms 44876 KB Output is correct
10 Correct 217 ms 44936 KB Output is correct
11 Correct 258 ms 44936 KB Output is correct
12 Correct 222 ms 44932 KB Output is correct
13 Correct 286 ms 44948 KB Output is correct
14 Correct 260 ms 44940 KB Output is correct
15 Correct 267 ms 44948 KB Output is correct
16 Correct 263 ms 44952 KB Output is correct
17 Correct 263 ms 44948 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 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 228 ms 692 KB Output is correct
11 Correct 117 ms 620 KB Output is correct
12 Correct 19 ms 948 KB Output is correct
13 Correct 256 ms 704 KB Output is correct
14 Correct 159 ms 628 KB Output is correct
15 Correct 255 ms 876 KB Output is correct
16 Correct 269 ms 44944 KB Output is correct
17 Correct 294 ms 44956 KB Output is correct
18 Correct 258 ms 44952 KB Output is correct
19 Correct 273 ms 44952 KB Output is correct
20 Correct 264 ms 44836 KB Output is correct
21 Correct 269 ms 44956 KB Output is correct
22 Correct 269 ms 44936 KB Output is correct
23 Correct 252 ms 44952 KB Output is correct
24 Correct 209 ms 44876 KB Output is correct
25 Correct 217 ms 44936 KB Output is correct
26 Correct 258 ms 44936 KB Output is correct
27 Correct 222 ms 44932 KB Output is correct
28 Correct 286 ms 44948 KB Output is correct
29 Correct 260 ms 44940 KB Output is correct
30 Correct 267 ms 44948 KB Output is correct
31 Correct 263 ms 44952 KB Output is correct
32 Correct 263 ms 44948 KB Output is correct
33 Incorrect 267 ms 37924 KB Output isn't correct
34 Halted 0 ms 0 KB -