Submission #247459

#	Time	Username	Problem	Language	Result	Execution time	Memory
247459		srvlt	Werewolf (IOI18_werewolf)	C++14	0 / 100	865 ms	45432 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 = 2e5 + 123;
int deg[n], used[n], pos[n], a[n], fl[n], fr[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 + n];

struct Node {
	int l = 0, r = 0, mx, mn;
	void clean() {
		mn = n, mx = -1;
	}
	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]);
}

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 < N; i++) {
		//cout << a[i] << ' ';
	//}
	//cout << '\n';
	for (int i = 0; i < Q; i++)
		q[i].l = L[i], 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[q[i].ind] = tmp.mx + 1;
			q[i].l = -R[q[i].ind];
		}	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[q[i].ind] = tmp.mn - 1;
		}	else upd(1, q[i].ind + 1);
	}
  for (int i = 0; i < Q; i++) {
	  //cout << "fl fr " << fl[i] << ' ' << fr[i] << '\n';
	  A[i] = !(fl[i] < fr[i]);
  }
}	else assert(false);
  return A;
}
/*
7 6 1
2 3
3 0
0 1
6 2
4 5
4 1
1 6 2 3
*/

Compilation message (stderr)

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

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