Submission #791141

#	Time	Username	Problem	Language	Result	Execution time	Memory
791141		AkramElOmrani	Werewolf (IOI18_werewolf)	C++17	0 / 100	525 ms	524288 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;


template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);


vector<int> lg;
struct Sparse1 {
	int n;
	int LOG;
	vector<vector<int>> table;
	Sparse1(vector<int>& a) {
		n = a.size();
		LOG = (int)(log2(n)) + 1;
		table = vector<vector<int>>(n, vector<int>(LOG));
		for(int i = 0; i < n; ++i) {
			table[i][0] = a[i];
		}
		for(int j = 1; j < LOG; ++j) {
			for(int i = 0; i + (1 << j) <= n; ++i) {
				table[i][j] = min(table[i][j - 1], table[(1 << (j - 1)) + i][j - 1]);
			}
		}
	}
	int get(int low, int high) {
		int sz = (high - low + 1);
		int l = lg[sz];
		return min(table[low][l], table[high - (1 << l) + 1][l]);
	}
};

struct Sparse2 {
	int n;
	int LOG;
	vector<vector<int>> table;
	Sparse2(vector<int>& a) {
		n = a.size();
		LOG = (int)(log2(n)) + 1;
		table = vector<vector<int>>(n, vector<int>(LOG));
		for(int i = 0; i < n; ++i) {
			table[i][0] = a[i];
		}
		for(int j = 1; j < LOG; ++j) {
			for(int i = 0; i + (1 << j) <= n; ++i) {
				table[i][j] = max(table[i][j - 1], table[(1 << (j - 1)) + i][j - 1]);
			}
		}
	}
	int get(int low, int high) {
		int sz = (high - low + 1);
		int l = lg[sz];
		return max(table[low][l], table[high - (1 << l) + 1][l]);
	}
};

std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,
								std::vector<int> s, std::vector<int> e,
								std::vector<int> l, std::vector<int> r) {

	lg.resize(n + 1);
	for(int i = 2; i <= n; ++i) {
		lg[i] = lg[i / 2] + 1;
	}
	int q = s.size();
	vector<int> a(q);

	vector<vector<int>> adj(n);
	for(int i = 0; i < x.size(); ++i) {
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}

	int root = 0;
	for(int i = 0; i < n; ++i) {
		if(adj.size() == 1) {
			root = i;
			break;
		}
	}

	// dbg(adj)
	// dbg(root)
	vector<int> arr;
	vector<int> inv(n);
	function<void(int, int)> build = [&](int node, int p = -1) {
		// dbg(node)
		inv[node] = (int)arr.size();
		arr.push_back(node);
		for(int x : adj[node]) {
			if(p == x) continue;
			build(x, node);
		}
	};

	build(root, -1);
	Sparse1 mn(arr);
	Sparse2 mx(arr);
	// dbg(inv)
	// dbg(arr)

	for(int i = 0; i < q; ++i) {
		int s_l = inv[s[i]];
		int s_r = inv[e[i]];
		// dbg(s_l, s_r)

		if(s_l <= s_r) {
			int low = s_l, high = s_r; // max to human
			while(low < high) {
				int mid = (low + high + 1) / 2;
				if(mn.get(s_l, mid) >= l[i]) {
					low = mid;
				} else {
					high = mid - 1;
				}
			}
			int f = high;
			low = s_l, high = s_r; // max to wolf
			while(low < high) {
				int mid = (low + high) / 2;
				if(mx.get(mid, s_r) <= r[i]) {
					high = mid;
				} else {
					low = mid + 1;
				}
			}
			int s = low;
			if(f <= s) {
				a[i] = 1;
			}
		}
		else {
			swap(s_l, s_r);
			int low = s_l, high = s_r; // min to human
			while(low < high) {
				int mid = (low + high) / 2;
				if(mn.get(mid, s_r) >= l[i]) {
					high = mid;
				} else {
					low = mid + 1;
				}
			}
			int s = high;
			low = s_l, high = s_r; // max to wolf
			while(low < high) {
				int mid = (low + high + 1) / 2;
				if(mx.get(s_l, mid) <= r[i]) {
					low = mid;
				} else {
					high = mid - 1;
				}
			}
			int f = low;
			if(s <= f) {
				a[i] = 1;
			}
		}
	}
	return a;
}


/*
6 5 3
4 3
1 2
3 1
5 4
0 2

4 2 2 2
0 5 2 5
0 5 1 5
*/

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:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i = 0; i < x.size(); ++i) {
      |                 ~~^~~~~~~~~~

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