結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー | otoshigo |
提出日時 | 2024-02-16 21:59:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 818 ms / 2,500 ms |
コード長 | 2,127 bytes |
コンパイル時間 | 848 ms |
コンパイル使用メモリ | 85,140 KB |
実行使用メモリ | 83,584 KB |
最終ジャッジ日時 | 2024-02-16 22:00:04 |
合計ジャッジ時間 | 11,576 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 183 ms
22,016 KB |
testcase_01 | AC | 510 ms
43,776 KB |
testcase_02 | AC | 695 ms
76,160 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 2 ms
6,676 KB |
testcase_05 | AC | 2 ms
6,676 KB |
testcase_06 | AC | 169 ms
13,184 KB |
testcase_07 | AC | 574 ms
82,432 KB |
testcase_08 | AC | 544 ms
73,600 KB |
testcase_09 | AC | 607 ms
83,584 KB |
testcase_10 | AC | 763 ms
83,584 KB |
testcase_11 | AC | 806 ms
83,584 KB |
testcase_12 | AC | 818 ms
83,584 KB |
testcase_13 | AC | 760 ms
83,584 KB |
testcase_14 | AC | 818 ms
83,584 KB |
testcase_15 | AC | 159 ms
6,676 KB |
testcase_16 | AC | 158 ms
6,676 KB |
testcase_17 | AC | 158 ms
6,676 KB |
testcase_18 | AC | 332 ms
26,240 KB |
testcase_19 | AC | 485 ms
64,896 KB |
testcase_20 | AC | 440 ms
53,760 KB |
testcase_21 | AC | 550 ms
83,584 KB |
ソースコード
#include<iostream> #include<algorithm> #include<vector> using namespace std; using ll=long long; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} struct UnionFind { private: vector<int> par, siz; public: UnionFind(){} UnionFind(int n) : par(n, -1), siz(n, 1) {} int find(int x) { if (par[x] == -1) return x; else { par[x] = find(par[x]); return par[x]; } } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return siz[find(x)]; } bool merge(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin>>N>>M; vector<int>A(M),B(M); for(int i=0;i<M;i++){ cin>>A[i]>>B[i]; A[i]--; B[i]--; } vector<int>C(N); for(int i=0;i<N;i++){ cin>>C[i]; C[i]--; } vector<ll>W(10); for(int i=0;i<10;i++)cin>>W[i]; int Q; cin>>Q; vector<UnionFind>ufs(1<<10); for(int i=0;i<1<<10;i++){ UnionFind uf(N); ufs[i]=uf; } for(int bit=0;bit<1<<10;bit++){ for(int i=0;i<M;i++){ if((bit>>C[A[i]]&1)&&(bit>>C[B[i]]&1)){ ufs[bit].merge(A[i],B[i]); } } } vector<ll>Bs(1<<10); for(int bit=0;bit<1<<10;bit++){ for(int i=0;i<10;i++){ if(bit>>i&1)Bs[bit]+=W[i]; } } while(Q--){ int u,v; cin>>u>>v; u--; v--; ll ans=1LL<<60; for(int bit=0;bit<1<<10;bit++){ if(ufs[bit].same(u,v)){ chmin(ans,Bs[bit]); } } if(ans==1LL<<60)cout<<-1<<"\n"; else cout<<ans<<"\n"; } }