Submission #251100

#	Time	Username	Problem	Language	Result	Execution time	Memory
251100		kostia244	Werewolf (IOI18_werewolf)	C++17	100 / 100	1793 ms	175512 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 1<<18;
using vi = vector<int>;
int TIME = -1;
struct dsu {
	vi r, p;
	vector<vi> ch;
	vector<array<int, 2>> range;
	vector<vector<array<int, 2>>> h;
	dsu(int n) : r(n, 1), ch(n), h(n), p(n), range(n) {
		iota(all(p), 0);
		fill(all(range), array<int, 2>{0, 1});
		for(int i = 0; i < n; i++) ch[i].push_back(i), h[i].push_back({n+1, i});
	}
	int par(int i) {
		return i == p[i] ? i : p[i] = par(p[i]);
	}
	void unite(int i, int j) {
		i = par(i), j = par(j);
		if(i == j) return;
		if(r[i] < r[j]) swap(i, j);
		p[j] = i;
		range[i][1] += r[j];
		for(auto v : ch[j]) {
			ch[i].push_back(v);
			h[v].push_back({TIME, i});
			range[v][0] += r[i];
		}
		r[i] += r[j];
	}
};
vi g[maxn], gt[maxn];
vi cl[maxn], cr[maxn], ev[maxn];
array<int, 2> range[maxn];
set<array<int, 2>> req[maxn];
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
	int q = s.size();
	vi ans(q), ipar(q), tp(q);
	for(int i = 0; i < x.size(); i++) {
		if(x[i] < y[i]) swap(x[i], y[i]);
		g[x[i]].push_back(y[i]);
		gt[y[i]].push_back(x[i]);
	}
	for(int i = 0; i < q; i++)
		cl[l[i]].push_back(i), cr[r[i]].push_back(i);
	dsu f(n), b(n);
	for(int i = 0; i < n; i++) {
		for(auto v : g[i]) f.unite(i, v);
		for(auto j : cr[i]) {
			tp[j] = f.par(e[j]);
			range[j] = f.range[tp[j]];
		}
	}
	for(int j = 0; j < q; j++) {
		int t = tp[j];
		range[j][1] -= range[j][0];
		range[j][0] = f.range[t][0];
		range[j][1] += f.range[t][0];
		ev[range[j][0]].push_back(j);
		ev[range[j][1]].push_back(-j-1);
		//cout << e[j] << " " << range[j][0] << " " << range[j][1] << '\n';
	}
	for(int i = n; i--;) {
		TIME = i;
		for(auto v : gt[i]) b.unite(i, v);
		for(auto j : cl[i]) ipar[j] = b.par(s[j]);//, cout << j << " " << ipar[j] << '\n';
	}
	vi ord(n);
	for(int i = 0; i < n; i++) ord[f.range[i][0]] = i;
	ord.push_back(-1);
	int T = 0;
	for(auto i : ord) {
		for(auto j : ev[T])
			if(j >= 0) {
				int p = ipar[j];
				req[p].insert({l[j], j});
			} else {
				j = -(j+1);
				//cout << "REMOVE " << j << " " << T << endl;
				int p = ipar[j];
				if(req[p].count({l[j], j})) ans[j] = 1, req[p].erase({l[j], j});
				ans[j] ^= 1;
			}
		if(i == -1) break;
		//cout << i << " :\n";
		for(auto [t, p] : b.h[i]) {
			//cout << t << " " << p << "p\n";
			while(!req[p].empty() && req[p].begin()->at(0) <= t) {
				//cout << " Moment " << T << " " << range[req[p].begin()->at(1)][1] << '\n';
				req[p].erase(req[p].begin());
			}
		}
		//cout << '\n';
		++T;
	}
	//for(int i = 0; i < q; i++) ans[i] &= s[i] >= l[i] && e[i] <= r[i], cout << i << " " << (s[i] >= l[i]) << " " << (e[i] <= r[i]) << '\n';
	return ans;
}

Compilation message (stderr)

werewolf.cpp: In constructor 'dsu::dsu(int)':
werewolf.cpp:12:32: warning: 'dsu::h' will be initialized after [-Wreorder]
  vector<vector<array<int, 2>>> h;
                                ^
werewolf.cpp:9:8: warning:   'vi dsu::p' [-Wreorder]
  vi r, p;
        ^
werewolf.cpp:13:2: warning:   when initialized here [-Wreorder]
  dsu(int n) : r(n, 1), ch(n), h(n), p(n), range(n) {
  ^~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < x.size(); i++) {
                 ~~^~~~~~~~~~

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