Submission #418817

#	Time	Username	Problem	Language	Result	Execution time	Memory
418817		peuch	Werewolf (IOI18_werewolf)	C++17	0 / 100	2004 ms	70544 KiB

werewolf

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

const int MAXN = 2e6 + 10;

int n;
int in[MAXN];
vector<int> ar[MAXN];
vector<int> ord;
vector<int> id;
pair<int, int> seg[4 * MAXN];
int cnt;
int freq[MAXN];

void build(int pos, int ini, int fim){
	if(ini == fim){
		seg[pos] = make_pair(ord[ini], ord[ini]);
		return;
	}	
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	build(e, ini, mid);
	build(d, mid + 1, fim);
	seg[pos].first = max(seg[e].first, seg[d].first);
	seg[pos].second = min(seg[e].second, seg[d].second);
}

pair<int, int> query(int pos, int ini, int fim, int p, int q){
	cnt++;
	if(ini > q || fim < p) return make_pair(-1, n + 1);
	if(ini >= p && fim <= q) return seg[pos];
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	pair<int, int> eVal = query(e, ini, mid, p, q);
	pair<int, int> dVal = query(d, mid + 1, fim, p, q);
	pair<int, int> ret;
	ret.first = max(eVal.first, dVal.first);
	ret.second = min(eVal.second, dVal.second);
	return ret;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
	n = N;
	for(int i = 0; i < X.size(); i++){
		ar[X[i]].push_back(Y[i]);
		ar[Y[i]].push_back(X[i]);
		in[X[i]]++;
		in[Y[i]]++;
	}
	if(X.size() != N - 1) return vector<int> (E.size());
	for(int i = 0; i < n; i++){
		if(in[i] != 1) continue;
		ord.clear();
		int cur = i;
		int pai = i;
		do{
			ord.push_back(cur);
			for(int i = 0; i < ar[cur].size(); i++){
				int viz = ar[cur][i];
				if(viz == pai) continue;
				pai = cur;
				cur = viz;
				break;
			}
		}
		while(in[cur] != 1);
		break;
	}
//	printf("Iniciou\n");
//	fflush(stdout);
	id = vector<int> (n);
	for(int i = 0; i < ord.size(); i++){
		id[ord[i]] = i;
	}
	vector<int> ans(E.size());
	build(1, 0, n - 1);
	for(int i = 0; i < E.size(); i++){
		int a = id[S[i]];
		int b = id[E[i]];
		if(a < b){
			int ini = a, fim = b;
			while(ini != fim){
				int mid = (ini + fim) >> 1;
				if(ini == fim - 1) mid = fim;
				pair<int, int> qVal = query(1, 0, n - 1, a, mid);
				if(qVal.second >= L[i]) ini = mid;
				else fim = mid - 1;
			}
			pair<int, int> qVal = query(1, 0, n - 1, ini, b);
			ans[i] = qVal.first <= R[i];
		}	
		else{
			int ini = b, fim = a;
			while(ini != fim){
				int mid = (ini + fim) >> 1;
				if(ini == fim - 1) mid = fim;
				pair<int, int> qVal = query(1, 0, n - 1, b, mid);
				if(qVal.first <= R[i]) ini = mid;
				else fim = mid - 1;
			}
			pair<int, int> qVal = query(1, 0, n - 1, ini, a);
			ans[i] = qVal.second >= L[i];
		}
//		printf("%d\n", ans[i]);
	}
//	fprintf(stderr, "%d\n", cnt);
	return ans;
}

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:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0; i < X.size(); i++){
      |                 ~~^~~~~~~~~~
werewolf.cpp:49:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |  if(X.size() != N - 1) return vector<int> (E.size());
      |     ~~~~~~~~~^~~~~~~~
werewolf.cpp:57:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for(int i = 0; i < ar[cur].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~
werewolf.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0; i < ord.size(); i++){
      |                 ~~^~~~~~~~~~~~
werewolf.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0; i < E.size(); i++){
      |                 ~~^~~~~~~~~~

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