oj.uz

답안 #829180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829180 2023-08-18T06:06:18 Z tranxuanbach 늑대인간 (IOI18_werewolf) C++17
15 / 100
 427 ms 171736 KB 
#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

#define isz(a) ((signed)a.size())

constexpr int N = 2e5 + 5, M = 4e5 + 5, Q = 2e5 + 5;
constexpr int NODE = 4e5 + 5;
constexpr int inf = 1e9 + 7;

struct merge_sort_tree{
	vector <int> seg[1 << 19];

	void build(int id, int l, int r, int a[]){
		if (l == r){
			seg[id].emplace_back(a[l]);
			return;
		}
		int mid = (l + r) >> 1;
		build(id * 2, l, mid, a);
		build(id * 2 + 1, mid + 1, r, a);
		merge(seg[id * 2].begin(), seg[id * 2].end(), seg[id * 2 + 1].begin(), seg[id * 2 + 1].end(), back_inserter(seg[id]));
	}

	int query(int id, int l, int r, int u, int v, int val){
		if (v < l or r < u){
			return inf;
		}
		if (u <= l and r <= v){
			auto itr = lower_bound(seg[id].begin(), seg[id].end(), val);
			return itr == seg[id].end() ? inf : *itr;
		}
		int mid = (l + r) >> 1;
		return min(query(id * 2, l, mid, u, v, val), query(id * 2 + 1, mid + 1, r, u, v, val));
	}
} seg;

struct Disjoint_set{
	int par[N];

	void reset(int sz = N){
		fill(par, par + sz, -1);
	}

	Disjoint_set(){
		reset();
	}

	int root(int x){
		return par[x] < 0 ? x : (par[x] = root(par[x]));
	}

	bool share(int x, int y){
		return root(x) == root(y);
	}

	bool merge(int x, int y){
		if ((x = root(x)) == (y = root(y))){
			return false;
		}
		if (par[x] > par[y]){
			swap(x, y);
		}
		par[x] += par[y];
		par[y] = x;
		return true;
	}
};

struct Query{
	int s, t, l, r;
};

int n, m, q;
vector <int> adj[N];
Query query[Q];

vector <int> adj_werewolf[NODE], adj_human[NODE];
int root_werewolf, root_human;
int node_werewolf[Q], node_human[Q];

int ctrtour, tour[NODE], tin[NODE], tout[NODE];

void dfs_tour(vector <int> adj[], int u){
	tour[ctrtour] = u;
	tin[u] = ctrtour;
	ctrtour++;
	for (auto v: adj[u]){
		dfs_tour(adj, v);
	}
	tout[u] = ctrtour;
}

pair <int, int> tour_range_werewolf[Q], tour_range_human[Q];
int pos_human[N], pos_werewolf[N];
int pos[NODE];
int ans[Q];

vector <int> check_validity(int _n, vector <int> _u, vector <int> _v, vector <int> _s, vector <int> _e, vector <int> _l, vector <int> _r){
	n = _n;
	m = isz(_u);
	for (int i = 0; i < m; i++){
		int u = _u[i], v = _v[i];
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	q = isz(_s);
	for (int i = 0; i < q; i++){
		int s = _s[i], t = _e[i], l = _l[i], r = _r[i];
		query[i] = Query{s, t, l, r};
	}

	{ // Human
		vector <pair <int, int>> query_human;
		for (int i = 0; i < q; i++){
			query_human.emplace_back(query[i].l, i);
		}
		sort(query_human.begin(), query_human.end());

		Disjoint_set dsu;
		vector <int> current_node(n);
		iota(current_node.begin(), current_node.end(), 0);
		root_human = n;

		for (int u = n - 1; u >= 0; u--){
			for (auto v: adj[u]){
				if (v < u){
					continue;
				}
				if (not dsu.share(u, v)){
					int x = current_node[dsu.root(u)], y = current_node[dsu.root(v)];
					dsu.merge(u, v);
					adj_human[root_human].emplace_back(x);
					adj_human[root_human].emplace_back(y);
					current_node[dsu.root(u)] = root_human;
					root_human++;
				}
			}
			while (not query_human.empty() and query_human.back().first == u){
				int i = query_human.back().second;
				node_human[i] = current_node[dsu.root(query[i].s)];
				query_human.pop_back();
			}
		}
		ctrtour = 0;
		dfs_tour(adj_human, root_human - 1);
		for (int i = 0; i < q; i++){
			tour_range_human[i] = pair{tin[node_human[i]], tout[node_human[i]]};
		}
		for (int u = 0; u < n; u++){
			pos_human[u] = tin[u];
		}
	}
	{ // Werewolf
		vector <pair <int, int>> query_werewolf;
		for (int i = 0; i < q; i++){
			query_werewolf.emplace_back(query[i].r, i);
		}
		sort(query_werewolf.begin(), query_werewolf.end(), greater <>());

		Disjoint_set dsu;
		vector <int> current_node(n);
		iota(current_node.begin(), current_node.end(), 0);
		root_werewolf = n;

		for (int u = 0; u < n; u++){
			for (auto v: adj[u]){
				if (v > u){
					continue;
				}
				if (not dsu.share(u, v)){
					int x = current_node[dsu.root(u)], y = current_node[dsu.root(v)];
					dsu.merge(u, v);
					adj_werewolf[root_werewolf].emplace_back(x);
					adj_werewolf[root_werewolf].emplace_back(y);
					current_node[dsu.root(u)] = root_werewolf;
					root_werewolf++;
				}
			}
			while (not query_werewolf.empty() and query_werewolf.back().first == u){
				int i = query_werewolf.back().second;
				node_werewolf[i] = current_node[dsu.root(query[i].t)];
				query_werewolf.pop_back();
			}
		}
		ctrtour = 0;
		dfs_tour(adj_werewolf, root_werewolf - 1);
		for (int i = 0; i < q; i++){
			tour_range_werewolf[i] = pair{tin[node_werewolf[i]], tout[node_werewolf[i]]};
		}
		for (int u = 0; u < n; u++){
			pos_werewolf[u] = tin[u];
		}
	}

	fill(pos, pos + root_human, inf);
	for (int u = 0; u < n; u++){
		pos[pos_human[u]] = pos_werewolf[u];
	}
	seg.build(1, 0, root_human - 1, pos);
	for (int i = 0; i < q; i++){
		if (seg.query(1, 0, root_human - 1, tour_range_human[i].first, tour_range_human[i].second - 1, tour_range_werewolf[i].first) < tour_range_werewolf[i].second){
			ans[i] = 1;
		}
		else{
			ans[i] = 0;
		}
	}
	return vector <int>(ans, ans + q);
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 36932 KB Output is correct
2 Correct 18 ms 36948 KB Output is correct
3 Correct 17 ms 36984 KB Output is correct
4 Correct 19 ms 36956 KB Output is correct
5 Correct 17 ms 36896 KB Output is correct
6 Correct 19 ms 36880 KB Output is correct
7 Correct 17 ms 36980 KB Output is correct
8 Correct 18 ms 36880 KB Output is correct
9 Correct 20 ms 36884 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 36932 KB Output is correct
2 Correct 18 ms 36948 KB Output is correct
3 Correct 17 ms 36984 KB Output is correct
4 Correct 19 ms 36956 KB Output is correct
5 Correct 17 ms 36896 KB Output is correct
6 Correct 19 ms 36880 KB Output is correct
7 Correct 17 ms 36980 KB Output is correct
8 Correct 18 ms 36880 KB Output is correct
9 Correct 20 ms 36884 KB Output is correct
10 Correct 23 ms 38512 KB Output is correct
11 Correct 22 ms 38460 KB Output is correct
12 Correct 21 ms 38456 KB Output is correct
13 Correct 24 ms 38516 KB Output is correct
14 Correct 25 ms 38592 KB Output is correct
15 Correct 24 ms 38556 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 427 ms 171736 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 36932 KB Output is correct
2 Correct 18 ms 36948 KB Output is correct
3 Correct 17 ms 36984 KB Output is correct
4 Correct 19 ms 36956 KB Output is correct
5 Correct 17 ms 36896 KB Output is correct
6 Correct 19 ms 36880 KB Output is correct
7 Correct 17 ms 36980 KB Output is correct
8 Correct 18 ms 36880 KB Output is correct
9 Correct 20 ms 36884 KB Output is correct
10 Correct 23 ms 38512 KB Output is correct
11 Correct 22 ms 38460 KB Output is correct
12 Correct 21 ms 38456 KB Output is correct
13 Correct 24 ms 38516 KB Output is correct
14 Correct 25 ms 38592 KB Output is correct
15 Correct 24 ms 38556 KB Output is correct
16 Runtime error 427 ms 171736 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -