Submission #418768

#	Time	Username	Problem	Language	Result	Execution time	Memory
418768		peuch	Werewolf (IOI18_werewolf)	C++17	0 / 100	4056 ms	64420 KiB

werewolf

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

const int MAXN = 2e5 + 10;

struct event{
	int l, r, id;
	event(int _l = 0, int _r = 0, int _id = -1){
		l = _l;
		r = _r;
		id = _id;
	}
	bool operator < (event a){
		if(r == a.r) return id < a.id;
		return r < a.r;
	}
};

int n;

vector<int> rep, tam;
stack<int> pilha;
vector<pair<int, int> > seg[4 * MAXN];

void uni(int a, int b);
void rollback();
int find(int a);
void update(int pos, int ini, int fim, int p, int q, pair<int, int> val);
int query(int pos, int ini, int fim, int id, int x, int y);

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;
	int q = L.size();
	int m = X.size();
	
	rep = vector<int> (n);
	tam = vector<int> (n, 1);
	for(int i = 0; i < n; i++)
		rep[i] = i;
	
	vector<int> ans(q);
	vector<event> ord;
	for(int i = 0; i < m; i++){
		if(X[i] > Y[i]) swap(X[i], Y[i]);
		update(1, 0, n - 1, 0, X[i], make_pair(X[i], Y[i]));
		ord.push_back(event(X[i], Y[i]));
	}
	for(int i = 0; i < q; i++)
		ord.push_back(event(L[i], R[i], i));
	sort(ord.begin(), ord.end());
	
	for(int i = 0; i < ord.size(); i++){
		if(ord[i].id == -1)
			update(1, 0, n - 1, 0, n - 1, make_pair(ord[i].l, ord[i].r));
		else
			ans[ord[i].id] = query(1, 0, n - 1, ord[i].l, S[ord[i].id], E[ord[i].id]);
	}
	return ans;
}

void uni(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b){
		pilha.push(-1);
		return;
	}
	if(tam[a] < tam[b]) swap(a, b);
	pilha.push(b);
	rep[b] = a;
	tam[a] += tam[b];
}

void rollback(){
	int a, b;
	b = pilha.top();
	pilha.pop();
	if(b == -1) return;
	a = rep[b];
	tam[a] -= tam[b];
	rep[b] = b;
}

int find(int a){
	if(a == rep[a]) return a;
	return find(rep[a]);
}

void update(int pos, int ini, int fim, int p, int q, pair<int, int> val){
	if(ini > q || fim < p) return;
	if(ini >= p && fim <= q){
		seg[pos].push_back(val);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	update(e, ini, mid, p, q, val);
	update(d, mid + 1, fim, p, q, val);
}

int query(int pos, int ini, int fim, int id, int x, int y){
	for(int i = 0; i < seg[pos].size(); i++)
		uni(seg[pos][i].first, seg[pos][i].second);
	int ret;
	if(ini == fim) ret = find(x) == find(y);
	else{
		int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
		if(id <= mid) ret = query(e, ini, mid, id, x, y);
		else ret = query(d, mid + 1, fim, id, x, y);
	}
	for(int i = 0; i < seg[pos].size(); i++)
		rollback();
	return ret;
}

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:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i = 0; i < ord.size(); i++){
      |                 ~~^~~~~~~~~~~~
werewolf.cpp: In function 'int query(int, int, int, int, int, int)':
werewolf.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = 0; i < seg[pos].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
werewolf.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int i = 0; i < seg[pos].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~

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