oj.uz

답안 #116728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116728 2019-06-13T16:35:06 Z Sorting 늑대인간 (IOI18_werewolf) C++14
34 / 100
 1335 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 7;
const int LOGN = 20;

vector<int> adj[MAXN], ans;
pair<bool, int> dp[MAXN][2];
int to, l, r, idx;

int min_table[MAXN][LOGN], max_table[MAXN][LOGN];
int a[MAXN], ptr[MAXN], n = 0;

bool solve(int u, bool stage){
	pair<bool, int> &p = dp[u][stage];

	if(p.second == idx){
		return p.first;
	}
	if(u == to){
		if(stage || (u >= l &&  u <= r)){
			return true;
		}
		return false;
	}
	if(!stage && u < l){
		return false;
	}
	if(stage && u > r){
		return false;
	}

	p.second = idx;
	p.first = false;

	if(!stage && u <= r){
		if(solve(u, true)){
			p.first = true;

			return true;
		}
	}

	for(int v: adj[u]){
		if(solve(v, stage)){
			p.first = true;

			return true;
		}
	}

	return false;
}

void make_a(int i, int pr = -1){
	a[n++] = i;
	for(int v: adj[i]){
		if(v != pr){
			make_a(v, i);
		}
	}
}

void init_table(){
	for(int i = 0; i < n; i++){
		min_table[i][0] = a[i];
		max_table[i][0] = a[i];
	}

	for(int j = 1; j < LOGN; j++){
		for(int i = 0; i < n; i++){
			max_table[i][j] = max(max_table[i][j - 1], max_table[min(n - 1, i + (1 << (j - 1)))][j - 1]);
			min_table[i][j] = min(min_table[i][j - 1], min_table[min(n - 1, i + (1 << (j - 1)))][j - 1]);
		}
	}
}

int calc_min(int from, int to){
	int d = to - from + 1, x = 0;

	while((1 << x) <= d){
		x++;
	}
	x--;

	return min(min_table[from][x], min_table[to - (1 << x) + 1][x]);
}

int calc_max(int from, int to){
	int d = to - from + 1, x = 0;

	while((1 << x) <= d){
		x++;
	}
	x--;

	return max(max_table[from][x], max_table[to - (1 << x) + 1][x]);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
	for(int i = 0; i < X.size(); i++){
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	if(true){
	//if(N > 3000){
		for(int i = 0; i < N; i++){
			if(adj[i].size() == 1){
				make_a(i);
				break;
			}
		}

		//for(int i = 0; i < n; i++){
		//	cout << a[i] << " ";
		//}
		//cout << endl;

		init_table();

		for(int i = 0; i < n; i++){
			ptr[a[i]] = i;
		}

		for(int i = 0; i < (int)E.size(); i++){
			int s = ptr[S[i]], e = ptr[E[i]];

			l = L[i];
			r = R[i];

			//cout << s << " s e " << e << endl; 

			if(s > e){
				swap(s, e);

				int bl = s, br = e + 1;

				while(bl != br){
					int mid = (bl + br) / 2;

					if(calc_max(s, mid) > r){
						br = mid;
					}
					else{
						bl = mid + 1;
					}
				}
				br--;

				if(br < s){
					ans.push_back(false);
					continue;
				}

				bl = s;

				if(calc_max(bl, br) < l){
					ans.push_back(false);
					continue;
				}

				int right_end = br;

				while(bl != br){
					int mid = (bl + br + 1) / 2;

					if(calc_max(mid, right_end) < l){
						br = mid - 1;
					}
					else{
						bl = mid;
					}
				}

				if(calc_max(s, bl) > r || calc_min(bl, e) < l){
					ans.push_back(false);
				}
				else{
					ans.push_back(true);
				}
			}
			else{
				int bl = s, br = e + 1;

				while(bl != br){
					int mid = (bl + br) / 2;

					if(calc_min(s, mid) < l){
						br = mid;
					}
					else{
						bl = mid + 1;
					}
				}
				br--;

				if(br < s){
					ans.push_back(false);
					continue;
				}

				bl = s;

				if(calc_min(bl, br) > r){
					ans.push_back(false);
					continue;
				}

				int right_end = br;

				while(bl != br){
					int mid = (bl + br + 1) / 2;

					if(calc_min(mid, right_end) > r){
						br = mid - 1;
					}
					else{
						bl = mid;
					}
				}

				if(calc_min(s, bl) < l || calc_max(bl, e) > r){
					ans.push_back(false);
				}
				else{
					ans.push_back(true);
				}
			}
		}

		return ans;
	}

	for(int i = 0; i < S.size(); i++){
		to = E[i];
		l = L[i];
		r = R[i];

		idx = i + 1;

		ans.push_back(solve(S[i], false));
	}

	return ans;
}

/*vector<int> xv, yv, sv, ev, lv, rv;

int main(){
	int n, m;

	cin >> n >> m;

	for(int i = 0; i < m; i++){
		int x, y;

		cin >> x >> y;

		xv.push_back(x);
		yv.push_back(y);
	}

	int q;

	cin >> q;

	for(int i = 0; i < q; i++){
		int sx, ex, lx, rx;

		cin >> sx >> ex >> lx >> rx;

		sv.push_back(sx);
		ev.push_back(ex);
		lv.push_back(lx);
		rv.push_back(rx);
	}

	vector<int> res = check_validity(n, xv, yv, sv, ev, lv, rv);

	for(int t: res){
		cout << t << " ";
	}
	cout << endl;

	return 0;
}*/
/*
2 1
0 1
2
0 1 1 1
1 0 1 2
*/

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:102:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++){
                 ~~^~~~~~~~~~
werewolf.cpp:235:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i++){
                 ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1335 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1335 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 730 ms 70616 KB Output is correct
2 Correct 1100 ms 73068 KB Output is correct
3 Correct 1063 ms 73072 KB Output is correct
4 Correct 993 ms 73160 KB Output is correct
5 Correct 972 ms 73100 KB Output is correct
6 Correct 858 ms 73052 KB Output is correct
7 Correct 862 ms 73388 KB Output is correct
8 Correct 942 ms 73160 KB Output is correct
9 Correct 531 ms 72972 KB Output is correct
10 Correct 516 ms 73036 KB Output is correct
11 Correct 529 ms 73140 KB Output is correct
12 Correct 604 ms 73184 KB Output is correct
13 Correct 990 ms 73332 KB Output is correct
14 Correct 960 ms 73072 KB Output is correct
15 Correct 1000 ms 73184 KB Output is correct
16 Correct 1008 ms 73216 KB Output is correct
17 Correct 818 ms 73000 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1335 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -