oj.uz

Submission #547783

# Submission time Handle Problem Language Result Execution time Memory
547783 2022-04-11T18:14:42 Z vovamr Werewolf (IOI18_werewolf) C++14
15 / 100
 932 ms 524288 KB 
#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;
}

struct node {
	node *l = nullptr;
	node *r = nullptr;
	int s = 0;
	node() {}
	node(int x) : s(x) {}
};
inline void upd(node *v, int vl, int vr, int pos, int x) {
	if (vl == vr) return void(v->s += x);
	int m = vl + vr >> 1;
	if (pos <= m) {
		if (!v->l) v->l = new node();
		upd(v->l, vl, m, pos, x);
	}
	else {
		if (!v->r) v->r = new node();
		upd(v->r, m + 1, vr, pos, x);
	}
	v->s = 0;
	if (v->l) v->s += v->l->s;
	if (v->r) v->s += v->r->s;
}
inline int get(node *v, int vl, int vr, int l, int r) {
	if (!v || l > r) return 0;
	else if (vl == l && vr == r) return v->s;
	int m = vl + vr >> 1;
	int a = get(v->l, vl, m, l, min(r, m));
	int b = get(v->r, m + 1, vr, max(l, m + 1), r);
	return a + b;
}
node *t[4 * N]; int L = 0, R = N;
inline void upd(int v, int vl, int vr, int x, int y, int d) {
	if (!t[v]) t[v] = new node();
	upd(t[v], L, R, y, d);
	if (vl == vr) return;
	int m = vl + vr >> 1;
	if (x <= m) upd(2 * v + 1, vl, m, x, y, d);
	else upd(2 * v + 2, m + 1, vr, x, y, d);
}
inline int get(int v, int vl, int vr, int l, int r, int l1, int r1) {
	if (l > r) return 0;
	else if (vl == l && vr == r) return (!t[v] ? 0 : get(t[v], L, R, l1, r1));
	int m = vl + vr >> 1;
	int a = get(2 * v + 1, vl, m, l, min(r, m), l1, r1);
	int b = get(2 * v + 2, m + 1, vr, max(l, m + 1), r, l1, r1);
	return a + b;
}

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);

/*
	cout << '\n';
	for (int i = 0; i < n; ++i) cout << in1[i] << " " << in2[i] << '\n';
	cout << '\n';

	for (int i = 0; i < q; ++i) {
		cout << "query " << i + 1 << ": " << '\n';
		cout << "vertices >= l: [" << in1[rt1[i]] << ", " << out1[rt1[i]] << "]" << '\n';
		cout << "vertices <= r: [" << in2[rt2[i]] << ", " << out2[rt2[i]] << "]" << '\n';
		cout << '\n';
	}
	cout << '\n';
*/

	int me = ti1;
	ve<int> ans(q);
	for (int i = 0; i < n; ++i) upd(0, 0, me, in1[i], in2[i], 1);
	for (int i = 0; i < q; ++i) ans[i] = get(0, 0, me, in1[rt1[i]], out1[rt1[i]], in2[rt2[i]], out2[rt2[i]]) > 0;
	return ans;
}

Compilation message

werewolf.cpp: In function 'void upd(node*, int, int, int, int)':
werewolf.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  int m = vl + vr >> 1;
      |          ~~~^~~~
werewolf.cpp: In function 'int get(node*, int, int, int, int)':
werewolf.cpp:81:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |  int m = vl + vr >> 1;
      |          ~~~^~~~
werewolf.cpp: In function 'void upd(int, int, int, int, int, int)':
werewolf.cpp:91:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |  int m = vl + vr >> 1;
      |          ~~~^~~~
werewolf.cpp: In function 'int get(int, int, int, int, int, int, int)':
werewolf.cpp:98:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |  int m = vl + vr >> 1;
      |          ~~~^~~~
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:127:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |  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 &[v, u, l, r, id] : que) {
      |             ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 282444 KB Output is correct
2 Correct 143 ms 282440 KB Output is correct
3 Correct 137 ms 282120 KB Output is correct
4 Correct 127 ms 282060 KB Output is correct
5 Correct 129 ms 282460 KB Output is correct
6 Correct 152 ms 282420 KB Output is correct
7 Correct 132 ms 282500 KB Output is correct
8 Correct 131 ms 282452 KB Output is correct
9 Correct 131 ms 282388 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 282444 KB Output is correct
2 Correct 143 ms 282440 KB Output is correct
3 Correct 137 ms 282120 KB Output is correct
4 Correct 127 ms 282060 KB Output is correct
5 Correct 129 ms 282460 KB Output is correct
6 Correct 152 ms 282420 KB Output is correct
7 Correct 132 ms 282500 KB Output is correct
8 Correct 131 ms 282452 KB Output is correct
9 Correct 131 ms 282388 KB Output is correct
10 Correct 183 ms 295352 KB Output is correct
11 Correct 162 ms 294492 KB Output is correct
12 Correct 150 ms 292484 KB Output is correct
13 Correct 172 ms 296020 KB Output is correct
14 Correct 157 ms 296236 KB Output is correct
15 Correct 167 ms 293844 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 932 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 282444 KB Output is correct
2 Correct 143 ms 282440 KB Output is correct
3 Correct 137 ms 282120 KB Output is correct
4 Correct 127 ms 282060 KB Output is correct
5 Correct 129 ms 282460 KB Output is correct
6 Correct 152 ms 282420 KB Output is correct
7 Correct 132 ms 282500 KB Output is correct
8 Correct 131 ms 282452 KB Output is correct
9 Correct 131 ms 282388 KB Output is correct
10 Correct 183 ms 295352 KB Output is correct
11 Correct 162 ms 294492 KB Output is correct
12 Correct 150 ms 292484 KB Output is correct
13 Correct 172 ms 296020 KB Output is correct
14 Correct 157 ms 296236 KB Output is correct
15 Correct 167 ms 293844 KB Output is correct
16 Runtime error 932 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -