oj.uz

Submission #604408

# Submission time Handle Problem Language Result Execution time Memory
604408 2022-07-25T05:59:48 Z amunduzbaev Werewolf (IOI18_werewolf) C++17
34 / 100
 431 ms 524288 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++) cout<<used[j]<<" ";
			//~ cout<<"\n";
			//~ for(int j=0;j<n;j++) cout<<tmp[j]<<" ";
			//~ cout<<"\n";
			//~ 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; }
	}
	memset(tree.mn, -1, sizeof tree.mn);
	memset(tree.mx, -1, sizeof tree.mx);
	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);
			//~ cout<<vl<<" "<<val[p - 1]<<" "<<vr<<" "<<tree.get(p, pos[e])<<"\n";
			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 2
0 3
3 2
2 1
1 5
5 4
2 5 2 5
3 1 3 3

*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 237 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 237 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 374 ms 47976 KB Output is correct
2 Correct 323 ms 56412 KB Output is correct
3 Correct 373 ms 56480 KB Output is correct
4 Correct 431 ms 56408 KB Output is correct
5 Correct 346 ms 56460 KB Output is correct
6 Correct 371 ms 56408 KB Output is correct
7 Correct 368 ms 56584 KB Output is correct
8 Correct 312 ms 56480 KB Output is correct
9 Correct 288 ms 56496 KB Output is correct
10 Correct 274 ms 56464 KB Output is correct
11 Correct 296 ms 56404 KB Output is correct
12 Correct 299 ms 56512 KB Output is correct
13 Correct 341 ms 56476 KB Output is correct
14 Correct 396 ms 56484 KB Output is correct
15 Correct 345 ms 56596 KB Output is correct
16 Correct 344 ms 56408 KB Output is correct
17 Correct 426 ms 56476 KB Output is correct

Subtask #4
0 / 51.0

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