제출 #547783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
547783		vovamr	늑대인간 (IOI18_werewolf)	C++14	15 / 100	932 ms	524288 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;
}

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51