結果
| 問題 | No.2630 Colorful Vertices and Cheapest Paths |
| ユーザー |
 Aeren
|
| 提出日時 | 2024-02-16 21:38:39 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 484 ms / 2,500 ms |
| コード長 | 6,071 bytes |
| コンパイル時間 | 3,116 ms |
| コンパイル使用メモリ | 266,696 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-09-28 19:53:10 |
| 合計ジャッジ時間 | 10,016 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 |
ソースコード
// #pragma GCC optimize("O3,unroll-loops")#include <bits/stdc++.h>// #include <x86intrin.h>using namespace std;#if __cplusplus >= 202002Lusing namespace numbers;#endiftemplate<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 LOCALassert(0 <= id && id < (int)edge.size());assert(edge[id].from == u || edge[id].to == u);#endifreturn u ^ edge[id].from ^ edge[id].to;}int link(int u, int v, T w = {}){ // insert an undirected edgeint 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 edgeint 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 graphgraph 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;}/**/