結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー | Aeren |
提出日時 | 2024-02-16 21:36:18 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 6,056 bytes |
コンパイル時間 | 3,045 ms |
コンパイル使用メモリ | 267,800 KB |
実行使用メモリ | 606,336 KB |
最終ジャッジ日時 | 2024-09-28 19:50:51 |
合計ジャッジ時間 | 25,751 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 395 ms
142,336 KB |
testcase_01 | AC | 868 ms
305,280 KB |
testcase_02 | MLE | - |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 3 ms
6,816 KB |
testcase_06 | AC | 242 ms
76,800 KB |
testcase_07 | MLE | - |
testcase_08 | MLE | - |
testcase_09 | MLE | - |
testcase_10 | MLE | - |
testcase_11 | MLE | - |
testcase_12 | MLE | - |
testcase_13 | MLE | - |
testcase_14 | MLE | - |
testcase_15 | AC | 138 ms
12,032 KB |
testcase_16 | AC | 137 ms
11,904 KB |
testcase_17 | AC | 140 ms
12,032 KB |
testcase_18 | AC | 407 ms
174,592 KB |
testcase_19 | AC | 1,015 ms
464,512 KB |
testcase_20 | AC | 848 ms
381,824 KB |
testcase_21 | MLE | - |
ソースコード
// #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; } vector<long long> mask_cost(1 << 10); vector dsu(1 << 10, disjoint_set(n)); for(auto mask = 0; mask < 1 << 10; ++ mask){ for(auto c = 0; c < 10; ++ c){ if(mask >> c & 1){ mask_cost[mask] += cost[c]; } } for(auto [u, v, _]: g.edge){ if(mask >> color[u] & 1 && mask >> color[v] & 1){ dsu[mask].merge(u, v); } } } int qn; cin >> qn; for(auto qi = 0; qi < qn; ++ qi){ int u, v; cin >> u >> v, -- u, -- v; long long res = numeric_limits<long long>::max(); for(auto mask = 1; mask < 1 << 10; ++ mask){ if(mask >> color[u] & 1 && dsu[mask].share(u, v)){ res = min(res, mask_cost[mask]); } } if(res == numeric_limits<long long>::max()){ res = -1; } cout << res << "\n"; } return 0; } /* */