Submission #1135351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135351		alterio	Werewolf (IOI18_werewolf)	C++20	0 / 100	1266 ms	29620 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 2e5 + 100;

vector<int> g[mxn], a(mxn), id(mxn);

struct Node {
	int mx = -1, mn = mxn;

	Node operator + (Node a) {
		return {max(mx, a.mx), min(mn, a.mn)};
	}
} null;

struct SGT {

	vector<Node> sgt;

	SGT(int sz) {
		sgt.resize(sz * 4);
	}

	void build(int k, int l, int r) {
		if (l == r) {
			sgt[k] = {a[l], a[l]};
			return;
		}
		int mid = (l + r) / 2;
		build(k * 2, l, mid);
		build(k * 2 + 1, mid + 1, r);
		sgt[k] = sgt[k * 2] + sgt[k * 2 + 1];
	}

	Node get(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return null;
		int mid = (l + r) / 2;
		if (i <= l && r <= j) return sgt[k];
		return get(k * 2, l, mid, i, j) + get(k * 2 + 1, mid + 1, r, i, j);
	}

} sgt(mxn);

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int M = X.size();
	int Q = S.size();
    vector<int> A(Q);
	for (int i = 0; i < M; i++) {
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}
	int start = 0;
	for (int i = 0; i < N; i++) if (g[i].size() == 1) start = i;
	bool visited[N + 2];
	memset(visited, 0, sizeof(visited));
	int cnt = 0;
	while (!visited[start]) {
		visited[start] = 1;
		id[start] = cnt;
		a[cnt++] = start;
		for (auto x : g[start]) if (!visited[x]) start = x;
	}
	sgt.build(1, 0, N - 1);
	for (int i = 0; i < Q; i++) {
		int mxL, mnR;
		int l = id[S[i]], r = N;
		while (l + 1 < r) {
			int mid = (l + r) / 2;
			Node get = sgt.get(1, 0, N - 1, l, mid);
			if (get.mn >= l) l = mid;
			else r = mid;
		}
		mxL = l;
		l = -1, r = id[E[i]];
		while (l + 1 < r) {
			int mid = (l + r) / 2;
			Node get = sgt.get(1, 0, N - 1, mid, r);
			if (get.mx <= r) r = mid;
			else l = mid;
		}
		mnR = r;
		A[i] = (mxL >= mnR);
	}
    return A;
}

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