#951088 (C++23) No.2630 Colorful Vertices and Cheapest Paths

提出ソース

結果

問題	No.2630 Colorful Vertices and Cheapest Paths
ユーザー	Aeren
提出日時	2024-02-16 21:38:39
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	553 ms / 2,500 ms
コード長	6,071 bytes
コンパイル時間	4,698 ms
コンパイル使用メモリ	266,028 KB
実行使用メモリ	6,548 KB
最終ジャッジ日時	2024-02-16 21:38:53
合計ジャッジ時間	12,111 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	160 ms 6,548 KB
testcase_01	AC	373 ms 6,548 KB
testcase_02	AC	467 ms 6,548 KB
testcase_03	AC	2 ms 6,548 KB
testcase_04	AC	2 ms 6,548 KB
testcase_05	AC	2 ms 6,548 KB
testcase_06	AC	162 ms 6,548 KB
testcase_07	AC	445 ms 6,548 KB
testcase_08	AC	406 ms 6,548 KB
testcase_09	AC	484 ms 6,548 KB
testcase_10	AC	524 ms 6,548 KB
testcase_11	AC	525 ms 6,548 KB
testcase_12	AC	553 ms 6,548 KB
testcase_13	AC	523 ms 6,548 KB
testcase_14	AC	528 ms 6,548 KB
testcase_15	AC	196 ms 6,548 KB
testcase_16	AC	195 ms 6,548 KB
testcase_17	AC	194 ms 6,548 KB
testcase_18	AC	173 ms 6,548 KB
testcase_19	AC	318 ms 6,548 KB
testcase_20	AC	273 ms 6,548 KB
testcase_21	AC	411 ms 6,548 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif

template<class T>
struct graph{
	using Weight_t = T;
	struct Edge_t{
		int from, to;
		T cost;
	};
	int n;
	vector<Edge_t> edge;
	vector<vector<int>> adj;
	function<bool(int)> ignore;
	graph(int n = 1): n(n), adj(n){
		assert(n >= 1);
	}
	graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
		assert(n >= 1);
		if(undirected){
			for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
		}
		else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
	}
	graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
		assert(n >= 1);
		if(undirected){
			for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
		}
		else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
	}
	graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
		assert(n >= 1);
		for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
	}
	graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
		assert(n >= 1);
		for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
	}
	int operator()(int u, int id) const{
		#ifdef LOCAL
		assert(0 <= id && id < (int)edge.size());
		assert(edge[id].from == u || edge[id].to == u);
		#endif
		return u ^ edge[id].from ^ edge[id].to;
	}
	int link(int u, int v, T w = {}){ // insert an undirected edge
		int id = (int)edge.size();
		adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
		return id;
	}
	int orient(int u, int v, T w = {}){ // insert a directed edge
		int id = (int)edge.size();
		adj[u].push_back(id), edge.push_back({u, v, w});
		return id;
	}
	void clear(){
		for(auto [u, v, w]: edge){
			adj[u].clear();
			adj[v].clear();
		}
		edge.clear();
		ignore = {};
	}
	graph transposed() const{ // the transpose of the directed graph
		graph res(n);
		for(auto &e: edge) res.orient(e.to, e.from, e.cost);
		res.ignore = ignore;
		return res;
	}
	int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
		return (int)adj[u].size();
	}
	// The adjacency list is sorted for each vertex.
	vector<vector<int>> get_adjacency_list() const{
		vector<vector<int>> res(n);
		for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
			if(ignore && ignore(id)) continue;
			res[(*this)(u, id)].push_back(u);
		}
		return res;
	}
	void set_ignoration_rule(const function<bool(int)> &f){
		ignore = f;
	}
	void reset_ignoration_rule(){
		ignore = nullptr;
	}
	friend ostream &operator<<(ostream &out, const graph &g){
		for(auto id = 0; id < (int)g.edge.size(); ++ id){
			if(g.ignore && g.ignore(id)) continue;
			auto &e = g.edge[id];
			out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
		}
		return out;
	}
};

template<bool Enable_small_to_large = true>
struct disjoint_set{
	int n, _group_count;
	vector<int> p;
	vector<list<int>> group;
	disjoint_set(){ }
	disjoint_set(int n): n(n), _group_count(n), p(n, -1), group(n){ assert(n >= 0);
		for(auto i = 0; i < n; ++ i) group[i] = {i};
	}
	int make_set(){
		p.push_back(-1);
		group.push_back(list<int>{p});
		++ _group_count;
		return n ++;
	}
	int root(int u){
		return p[u] < 0 ? u : p[u] = root(p[u]);
	}
	bool share(int a, int b){
		return root(a) == root(b);
	}
	int size(int u){
		return -p[root(u)];
	}
	bool merge(int u, int v){
		u = root(u), v = root(v);
		if(u == v) return false;
		-- _group_count;
		if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
		p[u] += p[v], p[v] = u;
		group[u].splice(group[u].end(), group[v]);
		return true;
	}
	bool merge(int u, int v, auto act){
		u = root(u), v = root(v);
		if(u == v) return false;
		-- _group_count;
		bool swapped = false;
		if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
		p[u] += p[v], p[v] = u;
		group[u].splice(group[u].end(), group[v]);
		act(u, v, swapped);
		return true;
	}
	int group_count() const{
		return _group_count;
	}
	const list<int> &group_of(int u){
		return group[root(u)];
	}
	vector<vector<int>> group_up(){
		vector<vector<int>> g(n);
		for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
		g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
		return g;
	}
	void clear(){
		_group_count = n;
		fill(p.begin(), p.end(), -1);
		for(auto i = 0; i < n; ++ i) group[i] = {i};
	}
	friend ostream &operator<<(ostream &out, disjoint_set dsu){
		auto gs = dsu.group_up();
		out << "{";
		if(!gs.empty()) for(auto i = 0; i < (int)gs.size(); ++ i){
			out << "{";
			for(auto j = 0; j < (int)gs[i].size(); ++ j){
				out << gs[i][j];
				if(j + 1 < (int)gs[i].size()) out << ", ";
			}
			out << "}";
			if(i + 1 < (int)gs.size()) out << ", ";
		}
		return out << "}";
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n, m;
	cin >> n >> m;
	graph<int> g(n);
	for(auto i = 0; i < m; ++ i){
		int u, v;
		cin >> u >> v, -- u, -- v;
		g.link(u, v);
	}
	vector<int> color(n), cost(10);
	for(auto &c: color){
		cin >> c, -- c;
	}
	for(auto &x: cost){
		cin >> x;
	}
	int qn;
	cin >> qn;
	vector<array<int, 2>> q(qn);
	for(auto &[u, v]: q){
		cin >> u >> v, -- u, -- v;
	}
	vector<long long> res(qn, numeric_limits<long long>::max());
	disjoint_set dsu(n);
	for(auto mask = 1; mask < 1 << 10; ++ mask){
		dsu.clear();
		long long mask_cost = 0;
		for(auto c = 0; c < 10; ++ c){
			if(mask >> c & 1){
				mask_cost += cost[c];
			}
		}
		for(auto [u, v, _]: g.edge){
			if(mask >> color[u] & 1 && mask >> color[v] & 1){
				dsu.merge(u, v);
			}
		}
		for(auto qi = 0; qi < qn; ++ qi){
			auto [u, v] = q[qi];
			if(mask >> color[u] & 1 && dsu.share(u, v)){
				res[qi] = min(res[qi], mask_cost);
			}
		}
	}
	for(auto x: res){
		if(x == numeric_limits<long long>::max()){
			x = -1;
		}
		cout << x << "\n";
	}
	return 0;
}

/*

*/

yukicoder

結果

テストケース

ソースコード