Submission #247505

#	Time	Username	Problem	Language	Result	Execution time	Memory
247505		srvlt	Werewolf (IOI18_werewolf)	C++14	49 / 100	4062 ms	54008 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n = 4e5 + 123;
int deg[n], used[n], pos[n], a[n];
int fl[2][n], fr[2][n];
vector <int> g[n];

void dfs(int v) {
	used[v] = 1;
	a[pos[v]] = v;
	for (int to : g[v]) {
		if (used[to]) continue;
		pos[to] = pos[v] + 1;
		dfs(to);
	}
}

struct query {
	int l, ind, t = 0;
	bool operator < (const query & q) {
		if (l == q.l) return t > q.t;
		return l < q.l;
	}
};
query q[n];

struct Node {
	int l = 0, r = 0, mx, mn;
	void clean() {
		mn = n, mx = -n;
	}
	void merge(const Node & x, const Node & y) {
		mx = max(x.mx, y.mx);
		mn = min(x.mn, y.mn);
	}
};
Node t[(1 << 19) + 1];

void build(int v, int l, int r) {
	t[v].l = l, t[v].r = r;
	if (l == r) {
		t[v].clean();
		return;
	}
	int m = l + r >> 1;
	build(v << 1, l, m);
	build(v << 1 | 1, m + 1, r);
	t[v].merge(t[v << 1], t[v << 1 | 1]);
}
Node tmp;

void get(int v, int l, int r) {
	if (t[v].l > r || t[v].r < l) return;
	if (t[v].l >= l && t[v].r <= r) {
		tmp.merge(tmp, t[v]);
		return;
	}
	get(v << 1, l, r), get(v << 1 | 1, l, r);
}

void upd(int v, int pos) {
	if (t[v].l == t[v].r) {
		t[v].mx = t[v].mn = t[v].l - 1;
		return;
	}
	int m = t[v].l + t[v].r >> 1;
	if (pos <= m) upd(v << 1, pos);
	else upd(v << 1 | 1, pos);
	t[v].merge(t[v << 1], t[v << 1 | 1]);
}

int cnt[3003];

void go(int v, int x, int f) {
	if ((f == 0 && v < x) || (f == 1 && v > x)) return;
	used[v] = 1;
	cnt[v]++;
	for (int to : g[v]) {
		if (used[to]) continue;
		go(to, x, f);
	}
}

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 M = X.size();
  bool bamboo = (M == N - 1);
  for (int i = 0; i < M; i++) {
	  deg[X[i]]++, deg[Y[i]]++;
	  g[X[i]].pb(Y[i]), g[Y[i]].pb(X[i]);
  }
  int root = -1;
  for (int i = 0; i < N; i++) {
	  if (deg[i] > 2) bamboo = false;
	  if (deg[i] == 1) root = i;
  }
  int Q = S.size();
  vector<int> A(Q);
  if (bamboo) {
	dfs(root);
	for (int i = 0; i < Q; i++)
		q[i].l = L[i] - 1, q[i].ind = i;
	for (int i = 0; i < N; i++)
		q[i + Q].l = a[i], q[i + Q].ind = i, q[i + Q].t = 1;
	sort(q, q + N + Q);
	build(1, 1, N);
	for (int i = 0; i < N + Q; i++) {
		if (q[i].t == 0) {
			int l = pos[S[q[i].ind]], r = pos[E[q[i].ind]];
			if (l > r) swap(l, r);
			tmp.clean(), get(1, l + 1, r + 1);
			fl[0][q[i].ind] = tmp.mn - 1;
			fl[1][q[i].ind] = tmp.mx + 1;
			q[i].l = -(R[q[i].ind] + 1);
		}	else {
			upd(1, q[i].ind + 1);
			q[i].l = -q[i].l;
		}
	}
	sort(q, q + N + Q);
	build(1, 1, N);
	for (int i = 0; i < N + Q; i++) {
		if (q[i].t == 0) {
			int l = pos[S[q[i].ind]], r = pos[E[q[i].ind]];
			if (l > r) swap(l, r);
			tmp.clean(), get(1, l + 1, r + 1);
			fr[0][q[i].ind] = tmp.mn - 1;
			fr[1][q[i].ind] = tmp.mx + 1;
		}	else upd(1, q[i].ind + 1);
	}
  for (int i = 0; i < Q; i++) {
	  int l = pos[S[i]], r = pos[E[i]];
	  if (l > r) {
		  A[i] = (fr[0][i] >= fl[1][i]);
	  }	  else {
	      A[i] = (fl[0][i] >= fr[1][i]);
	  }
  }
}	else {
	for (int i = 0; i < Q; i++) {
		memset(& cnt, 0, sizeof(cnt));
		memset(& used, 0, sizeof(used));
		int v = S[i], u = E[i];
		go(v, L[i], 0);
		memset(& used, 0, sizeof(used));
		go(u, R[i], 1);
		A[i] = 0;
		for (int j = 0; j < N; j++)
			if (cnt[j] >= 2) A[i] = 1;
	}
}
  return A;
}
/*
7 6 2
2 3
3 0
0 1
6 2
4 5
4 1
1 6 2 3
6 1 2 3

6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Compilation message (stderr)

werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:57:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
werewolf.cpp: In function 'void upd(int, int)':
werewolf.cpp:78:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = t[v].l + t[v].r >> 1;
          ~~~~~~~^~~~~~~~

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