Submission #547787

#	Time	Username	Problem	Language	Result	Execution time	Memory
547787		vovamr	Werewolf (IOI18_werewolf)	C++14	100 / 100	848 ms	353928 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 6e6 + 200;

ve<int> gr1[N]; int p1[N], w1 = 0;
inline int par1(int v) { if (p1[v] == v) { return v; } return (p1[v] = par1(p1[v])); }
inline void add1(int a, int b) {
	a = par1(a), b = par1(b);
	if (a == b) return;
	int c = w1++;
	p1[a] = p1[b] = p1[c] = c;
	gr1[c].pb(a);
	if (a ^ b) gr1[c].pb(b);
} int ti1 = 0;
int in1[N], out1[N];
inline void dfs1(int v) {
	in1[v] = ti1++;
	for (auto &to : gr1[v]) dfs1(to);
	out1[v] = ti1 - 1;
}

ve<int> gr2[N]; int p2[N], w2 = 0;
inline int par2(int v) { if (p2[v] == v) { return v; } return (p2[v] = par2(p2[v])); }
inline void add2(int a, int b) {
	a = par2(a), b = par2(b);
	if (a == b) return;
	int c = w2++;
	p2[a] = p2[b] = p2[c] = c;
	gr2[c].pb(a);
	if (a ^ b) gr2[c].pb(b);
} int ti2 = 0;
int in2[N], out2[N];
inline void dfs2(int v) {
	in2[v] = ti2++;
	for (auto &to : gr2[v]) dfs2(to);
	out2[v] = ti2 - 1;
}

int fe[N];
inline void upd(int i, int x) { i += 3; for (; i < N; i += i & -i) fe[i] += x; }
inline int get(int i) { int ans = 0; i += 3; for (; i; i -= i & -i) { ans += fe[i]; } return ans; }
inline int get(int l, int r) { return get(r) - get(l - 1); }

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	int n = N;
	int m = sz(X); int q = sz(S);
	ve<array<int,3>> e(m);

	for (int i = 0; i < m; ++i) {
		int v, u;
		tie(v, u) = mpp(X[i], Y[i]);
		e[i] = {min(v, u), v, u};
	} sort(all(e));

	w1 = w2 = n;
	for (int i = 0; i < n; ++i) p1[i] = p2[i] = i;

	ve<array<int,5>> que(q);
	for (int i = 0; i < q; ++i) que[i] = {S[i], E[i], L[i], R[i], i};
	sort(all(que), [](const auto &a, const auto &b) { return a[2] > b[2]; });

	ve<int> rt1(q), rt2(q);

	int ptr = sz(e) - 1, ptr1 = 0;
	for (auto &[v, u, l, r, id] : que) {
		while (~ptr && e[ptr][0] >= l) {
			add1(e[ptr][1], e[ptr][2]);
			--ptr;
		} rt1[id] = par1(v);
	}

	for (int i = 0; i < m; ++i) {
		int v, u;
		tie(v, u) = mpp(X[i], Y[i]);
		e[i] = {max(v, u), v, u};
	} sort(all(e));

	sort(all(que), [](const auto &a, const auto &b) { return a[3] < b[3]; });
	for (auto &[v, u, l, r, id] : que) {
		while (ptr1 < sz(e) && e[ptr1][0] <= r) {
			add2(e[ptr1][1], e[ptr1][2]);
			++ptr1;
		} rt2[id] = par2(u);
	}

	for (int i = 0; i < w1; ++i) if (p1[i] == i) dfs1(i);
	for (int i = 0; i < w2; ++i) if (p2[i] == i) dfs2(i);

	ve<int> a(n), b(n);
	for (int i = 0; i < n; ++i) a[i] = in1[i], b[i] = in2[i];
	sort(all(a)), sort(all(b));
	a.erase(unique(all(a)), a.end());
	b.erase(unique(all(b)), b.end());

	ve<int> c(n), d(n);
	for (int i = 0; i < n; ++i) c[i] = lower_bound(all(a), in1[i]) - a.begin();
	for (int i = 0; i < n; ++i) d[i] = lower_bound(all(b), in2[i]) - b.begin();

	ve<array<int,5>> hui;
	for (int i = 0; i < q; ++i) {
		int l1 = in1[rt1[i]], r1 = out1[rt1[i]];
		int l2 = in2[rt2[i]], r2 = out2[rt2[i]];

		l1 = lower_bound(all(a), l1) - a.begin();
		r1 = upper_bound(all(a), r1) - a.begin() - 1;
		l2 = lower_bound(all(b), l2) - b.begin();
		r2 = upper_bound(all(b), r2) - b.begin() - 1;

		if (l1 > r1 || l2 > r2) continue;
		hui.pb({r2    , l1, r1, +1, i});
		hui.pb({l2 - 1, l1, r1, -1, i});
	}

	sort(all(hui));

	ve<pii> al(n);
	for (int i = 0; i < n; ++i) al[i] = {d[i], i};
	sort(all(al));

	ptr = 0;
	ve<int> ans(q);
	for (auto &[pos, l, r, sgn, id] : hui) {
		while (ptr < sz(al) && al[ptr].fi <= pos) {
			upd(c[al[ptr].se], +1);
			++ptr;
		} ans[id] += get(l, r) * sgn;
	}
	for (auto &i : ans) i = !!i;
	return ans;
}

#ifdef LOCAL
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}
#endif

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:84:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |  for (auto &[v, u, l, r, id] : que) {
      |             ^
werewolf.cpp:98:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |  for (auto &[v, u, l, r, id] : que) {
      |             ^
werewolf.cpp:141:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |  for (auto &[pos, l, r, sgn, id] : hui) {
      |             ^

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