Submission #108163

#	Time	Username	Problem	Language	Result	Execution time	Memory
108163		Noam527	Werewolf (IOI18_werewolf)	C++17	100 / 100	2366 ms	123432 KiB

werewolf

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

const int mxn = 2e5 + 5;

int n;
vector<int> g[mxn];
int num[mxn];
int denum[mxn];

int good[mxn];
int root[mxn], sz[mxn];

vector<int> compv[mxn];
vector<vector<int>> ranges[mxn];
vector<pair<int, int>> roots[mxn];

set<int> comps[mxn];

vector<int> add(int v) {
	good[v] = 1;
	vector<int> rtn;
	for (const auto &i : g[v])
		if (good[i])
			rtn.push_back(i);
	return rtn;
}

void numerate() {
	vector<int> a;
	for (int i = 0; i < n; i++) {
		num[i] = good[i] = 0;
		sz[i] = 1;
		root[i] = i;
		compv[i].push_back(i);
	}
	for (int i = n - 1; i >= 0; i--) {
		a = add(i);
		for (const auto &v : a) {
			// connect v, i
			int x = root[i], y = root[v];
			if (x == y) continue;
			if (sz[x] > sz[y]) swap(x, y);
			for (const auto &u : compv[x]) {
				root[u] = y;
				num[u] += sz[y];
				compv[y].push_back(u);
			}
			sz[y] += sz[x];
			compv[x].clear();
		}
	}
	for (int i = 0; i < n; i++)
		denum[num[i]] = i;
	for (int i = 0; i < n; i++) compv[i].clear();
	// numerated. now ranges
	for (int i = 0; i < n; i++) {
		good[i] = 0;
		sz[i] = 1;
		root[i] = i;
		compv[i].push_back(i);
		ranges[i].push_back({ n, num[i], num[i] });
		roots[i].emplace_back(n, i);
	}
	for (int i = n - 1; i >= 0; i--) {
		a = add(i);
		for (const auto &v : a) {
			int x = root[i], y = root[v];
			if (x == y) continue;
			if (sz[x] > sz[y]) swap(x, y);
			for (const auto &u : compv[x]) {
				root[u] = y;
				compv[y].push_back(u);
				roots[u].emplace_back(i, y);
			}
			sz[y] += sz[x];
			compv[x].clear();
			ranges[y].push_back({ i, min(ranges[x].back()[1], ranges[y].back()[1]), max(ranges[x].back()[2], ranges[y].back()[2]) });
		}
	}
}

pair<int, int> getrange(int time, int v) {
	int lo, hi, mid;
	lo = 0, hi = (int)roots[v].size() - 1;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (roots[v][mid].first >= time) lo = mid;
		else hi = mid - 1;
	}
	v = roots[v][lo].second;

	lo = 0, hi = (int)ranges[v].size() - 1;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (ranges[v][mid][0] >= time) lo = mid;
		else hi = mid - 1;
	}
	return{ ranges[v][lo][1], ranges[v][lo][2] };
}

struct query {
	int l, r, s, e, ind;
	query() {}
	query(int ll, int rr, int ss, int ee, int ii) : l(ll), r(rr), s(ss), e(ee), ind(ii) {}
	bool operator < (const query &a) const {
		return r < a.r;
	}
};

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++) {
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}
	
	numerate();
	if (OO) {
		/*
		cout << "numerated: ";
		for (int i = 0; i < n; i++) cout << num[i] << " "; cout << '\n';
		while (1) {
			cout << "L, v: ";
			int tim, v;
			cin >> tim >> v;
			pair<int, int> tmp = getrange(tim, v);
			cout << "[" << tmp.first << ", " << tmp.second << "]\n";
		}
		*/
	}

	for (int i = 0; i < n; i++) {
		good[i] = 0;
		sz[i] = 1;
		root[i] = i;
		comps[i].insert(num[i]);
	}
	vector<int> a;

	int q = S.size();
	vector<int> ans(q);
	vector<query> Q(q);
	for (int i = 0; i < q; i++)
		Q[i] = query(L[i], R[i], S[i], E[i], i);
	sort(Q.begin(), Q.end());
	int nxt = 0;
	for (const auto &i : Q) {
		if (OO) {
			cout << "processing query:\n";
			cout << "(S, E, L, R) = " << i.s << " " << i.e << " " << i.l << " " << i.r << '\n';
		}
		while (nxt <= i.r) {
			a = add(nxt);
			if (OO) {
				cout << nxt << " becomes good: ";
				for (const auto &j : a) cout << j << " "; cout << '\n';
			}
			for (const auto &v : a) {
				int x = root[nxt], y = root[v];
				if (OO) cout << "merging " << nxt << " " << v << " = " << x << " " << y << '\n';
				if (x == y) continue;
				if (sz[x] > sz[y]) swap(x, y);
				for (const auto &u : comps[x]) {
					root[denum[u]] = y;
					comps[y].insert(u);
				}
				sz[y] += sz[x];
				comps[x].clear();
			}
			nxt++;
		}
		if (OO) {
			cout << "roots: ";
			for (int j = 0; j < n; j++) cout << root[j] << " "; cout << '\n';
		}
		pair<int, int> tmp = getrange(i.l, i.s);
		auto it = comps[root[i.e]].lower_bound(tmp.first);
		if (it == comps[root[i.e]].end() || tmp.second < *it) ans[i.ind] = 0;
		else ans[i.ind] = 1;
	}
	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:123:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X.size(); i++) {
                  ~~^~~~~~~~~~
werewolf.cpp:167:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (const auto &j : a) cout << j << " "; cout << '\n';
     ^~~
werewolf.cpp:167:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for (const auto &j : a) cout << j << " "; cout << '\n';
                                               ^~~~
werewolf.cpp:185:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << root[j] << " "; cout << '\n';
    ^~~
werewolf.cpp:185:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int j = 0; j < n; j++) cout << root[j] << " "; cout << '\n';
                                                        ^~~~

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