Submission #116728

#	Time	Username	Problem	Language	Result	Execution time	Memory
116728		Sorting	Werewolf (IOI18_werewolf)	C++14	34 / 100	1335 ms	524288 KiB

werewolf

#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 (stderr)

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
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51