제출 #767263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
767263		amunduzbaev	늑대인간 (IOI18_werewolf)	C++17	15 / 100	271 ms	38668 KiB

werewolf

#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;
	vector<int> a;
	int N;
	
	ST(int N): N(N){
		//~ Min.resize(N << 2);
		//~ Max.resize(N << 2);
		a.resize(N);
	}
	
	void set(int i, int v){
		a[i] = v;
	}
	
	int first_less(int l, int r, int v){
		for(int i=l;i<=r;i++){
			if(a[i] < v) return i;
		}
		return -1;
	}
	int last_less(int l, int r, int v){
		for(int i=r;i>=l;i--){
			if(a[i] < v) return i;
		}
		return -1;
	}
	int first_big(int l, int r, int v){
		for(int i=l;i<=r;i++){
			if(a[i] > v) return i;
		}
		return -1;
	}
	int last_big(int l, int r, int v){
		for(int i=r;i>=l;i--){
			if(a[i] > v) return i;
		}
		return -1;
	}
	
	//~ 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 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++){
				//~ cout<<used_s[j]<<" ";
			//~ } cout<<"\n";
			//~ for(int j=0;j<n;j++){
				//~ cout<<used_e[j]<<" ";
			//~ } cout<<"\n";
			
			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 = 0;
	for(int i=0;i<n;i++){
		if((int)edges[i].size() == 1){
			root = i;
			break;
		}
	}
	
	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);
	
	for(int i=0;i<n;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 L = tree.first_less(l_, r_, l[j]);
			if(L == -1 || R == -1 || L + 1 < R){
				ans[j] = 1;
			}
		} else {
			int L = tree.first_big(r_, l_, r[j]);
			int R = tree.last_less(r_, l_, l[j]);
			if(L == -1 || R == -1 || L + 1 < R){
				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 2 2

*/

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51