oj.uz

Submission #604396

# Submission time Handle Problem Language Result Execution time Memory
604396 2022-07-25T05:40:30 Z amunduzbaev Werewolf (IOI18_werewolf) C++17
15 / 100
 368 ms 45812 KB 
#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;

const int N = 2e5 + 5;
vector<int> edges[N];
int c[N];

struct ST{
	int mn[N << 2], mx[N << 2];
	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { mn[x] = mx[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);
		mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	
	int get_f(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(mn[x] >= v) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(mn[x << 1] < v) return get_f(l, r, v, lx, m, x << 1);
			else return get_f(l, r, v, m + 1, rx, x << 1 | 1);
		} int m = (lx + rx) >> 1;
		int res = get_f(l, r, v, lx, m, x << 1);
		if(~res) return res;
		return get_f(l, r, v, m + 1, rx, x << 1 | 1);
	}
	int get_l(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(mn[x] >= v) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(mn[x << 1 | 1] < v) return get_l(l, r, v, m + 1, rx, x << 1 | 1);
			else return get_l(l, r, v, lx, m, x << 1);
		} int m = (lx + rx) >> 1;
		int res = get_l(l, r, v, m + 1, rx, x << 1 | 1);
		if(~res) return res;
		return get_l(l, r, v, lx, m, x << 1);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return mx[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
}tree;

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();
	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();
	vector<int> a(q);
	if(n <= 3000 && m <= 6000 && q <= 3000){
		for(int i=0;i<q;i++){
			int s = S[i], e = E[i], vl = L[i], vr = R[i];
			for(int i=0;i<n;i++){
				if(i < vl) c[i] = 0;
				if(vr < i) c[i] = 1;
				if(vl <= i && i <= vr) c[i] = 2;
			}
			
			vector<int> used(n);
			int t = 1;
			function<void(int)> dfs = [&](int u){
				used[u] = 1;
				for(auto x : edges[u]){
					if(used[x]) continue;
					if(c[x] == t || c[x] == 2){
						dfs(x);
					}
				}
			};
			
			dfs(s);
			vector<int> tmp = used; fill(used.begin(), used.end(), 0);
			t = 0;
			dfs(e);
			for(int j=0;j<n;j++){
				if(used[j] && tmp[j]){
					a[i] = 1;
				}
			}
		}
		
		return a;
	}
	
	int r = 0;
	for(int i=0;i<n;i++){
		if((int)edges[i].size() == 1) { r = i; break; }
	}
	
	vector<int> pos(n), val(n);
	function<void(int, int)> dfs = [&](int u, int p){
		for(auto x : edges[u]){
			if(x == p) continue;
			pos[x] = pos[u] + 1;
			dfs(x, u);
		}
	};
	pos[r] = 1;
	dfs(r, r);
	for(int i=0;i<n;i++){
		val[pos[i]] = i;
		tree.set(pos[i], i);
	}
	for(int i=0;i<q;i++){
		int s = S[i], e = E[i], vl = L[i], vr = R[i];
		if(pos[s] < pos[e]){
			int p = tree.get_f(pos[s], N, vl);
			p = min(p, pos[e] + 1);
			if(pos[s] < p && vl <= val[p - 1] && val[p - 1] <= vr && (p <= pos[e] ? tree.get(p, pos[e]) <= vr : true)){
				a[i] = 1;
			}
		} else {
			int p = tree.get_l(0, pos[s], vl);
			p = max(p, pos[e] - 1);
			if(p < pos[s] && vl <= val[p + 1] && val[p + 1] <= vr && (pos[e] <= p ? tree.get(pos[e], p) <= vr : true)){
				a[i] = 1;
			}
		}
	}
	
	return a;
}

/*

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

*/

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4924 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 335 ms 5316 KB Output is correct
11 Correct 211 ms 5272 KB Output is correct
12 Correct 32 ms 5460 KB Output is correct
13 Correct 368 ms 5336 KB Output is correct
14 Correct 275 ms 5280 KB Output is correct
15 Correct 256 ms 5464 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4924 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 335 ms 5316 KB Output is correct
11 Correct 211 ms 5272 KB Output is correct
12 Correct 32 ms 5460 KB Output is correct
13 Correct 368 ms 5336 KB Output is correct
14 Correct 275 ms 5280 KB Output is correct
15 Correct 256 ms 5464 KB Output is correct
16 Incorrect 365 ms 45812 KB Output isn't correct
17 Halted 0 ms 0 KB -