oj.uz

Submission #604402

# Submission time Handle Problem Language Result Execution time Memory
604402 2022-07-25T05:47:43 Z amunduzbaev Werewolf (IOI18_werewolf) C++17
15 / 100
 385 ms 45928 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 + 1);
	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(s == e) a[i] = 1;
		if(pos[s] < pos[e]){
			int p = tree.get_f(pos[s], N, vl);
			p = min(p, pos[e] + 1);
			if(vl <= val[p - 1] && val[p - 1] <= vr && (p <= pos[e] ? tree.get(p, pos[e]) <= vr : true)){
				a[i] = 1;
			}
		} if(pos[s] > pos[e]) {
			int p = tree.get_l(0, pos[s], vl);
			p = max(p, pos[e] - 1);
			if(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

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

*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 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 3 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 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 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 3 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 5312 KB Output is correct
11 Correct 224 ms 5276 KB Output is correct
12 Correct 30 ms 5460 KB Output is correct
13 Correct 342 ms 5324 KB Output is correct
14 Correct 251 ms 5272 KB Output is correct
15 Correct 256 ms 5456 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 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 3 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 5312 KB Output is correct
11 Correct 224 ms 5276 KB Output is correct
12 Correct 30 ms 5460 KB Output is correct
13 Correct 342 ms 5324 KB Output is correct
14 Correct 251 ms 5272 KB Output is correct
15 Correct 256 ms 5456 KB Output is correct
16 Incorrect 385 ms 45928 KB Output isn't correct
17 Halted 0 ms 0 KB -