oj.uz

답안 #767215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767215 2023-06-26T14:08:08 Z amunduzbaev 늑대인간 (IOI18_werewolf) C++17
15 / 100
 258 ms 28700 KB 
#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;
	int N;
	
	ST(int N): N(N){
		Min.resize(N << 2);
		Max.resize(N << 2);
	}
	
	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, nxt = edges[root][0];
	while(last + 1 < n){
		pos[nxt] = ++last;
		int cur = nxt;
		if(last + 1 < n){
			if(edges[nxt][0] == root) nxt = edges[nxt][1];
			else nxt = edges[nxt][0];
		}
		root = cur;
	}
	
	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

*/

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 224 ms 692 KB Output is correct
11 Correct 111 ms 620 KB Output is correct
12 Correct 17 ms 940 KB Output is correct
13 Correct 251 ms 692 KB Output is correct
14 Correct 153 ms 596 KB Output is correct
15 Correct 215 ms 968 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 224 ms 692 KB Output is correct
11 Correct 111 ms 620 KB Output is correct
12 Correct 17 ms 940 KB Output is correct
13 Correct 251 ms 692 KB Output is correct
14 Correct 153 ms 596 KB Output is correct
15 Correct 215 ms 968 KB Output is correct
16 Incorrect 258 ms 28700 KB Output isn't correct
17 Halted 0 ms 0 KB -