oj.uz

답안 #604407

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
604407 2022-07-25T05:56:59 Z amunduzbaev 늑대인간 (IOI18_werewolf) C++17
0 / 100
 350 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; }
	}
	
	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);
	}
	
	//~ cout<<r<<"\n";
	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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 251 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 251 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 350 ms 46004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 251 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -