結果

問題 No.2630 Colorful Vertices and Cheapest Paths
ユーザー GOTKAKOGOTKAKO
提出日時 2024-02-16 22:30:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 895 ms / 2,500 ms
コード長 1,691 bytes
コンパイル時間 3,579 ms
コンパイル使用メモリ 216,200 KB
実行使用メモリ 84,096 KB
最終ジャッジ日時 2024-02-16 22:31:03
合計ジャッジ時間 14,467 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 227 ms
22,144 KB
testcase_01 AC 510 ms
43,904 KB
testcase_02 AC 821 ms
76,544 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 3 ms
6,676 KB
testcase_05 AC 3 ms
6,676 KB
testcase_06 AC 202 ms
13,312 KB
testcase_07 AC 771 ms
82,816 KB
testcase_08 AC 743 ms
73,856 KB
testcase_09 AC 854 ms
84,096 KB
testcase_10 AC 854 ms
83,968 KB
testcase_11 AC 895 ms
83,968 KB
testcase_12 AC 853 ms
83,968 KB
testcase_13 AC 887 ms
83,968 KB
testcase_14 AC 880 ms
83,968 KB
testcase_15 AC 163 ms
6,676 KB
testcase_16 AC 160 ms
6,676 KB
testcase_17 AC 160 ms
6,676 KB
testcase_18 AC 327 ms
26,368 KB
testcase_19 AC 590 ms
65,280 KB
testcase_20 AC 522 ms
54,144 KB
testcase_21 AC 638 ms
84,096 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class UnionFind{
    public:
    vector<int> par,siz;
 
    void make(int N){
        par.resize(N,-1);
        siz.resize(N,1);
    }
 
    int root(int x){
        if(par.at(x) == -1) return x;
        else return par.at(x) = root(par.at(x));
    }
 
    void unite(int u, int v){
        u = root(u),v = root(v);
        if(u == v) return;
        if(siz.at(u) < siz.at(v)) swap(u,v);
 
        par.at(v) = u;
        siz.at(u) += siz.at(v);
    }
 
    bool issame(int u, int v){
        if(root(u) == root(v)) return true;
        else return false;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M; cin >> N >> M;

    vector<vector<int>> Graph(N);
    for(int i=0; i<M; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
    }
    vector<int> C(N);
    vector<long long> W(10);
    for(auto &c : C) cin >> c,c--;
    for(auto &w : W) cin >> w;
    vector<long long> cost(1024);
    vector<UnionFind> UF(1024);
    for(int i=0; i<1024; i++){
        UnionFind &uf = UF.at(i);
        uf.make(N); 
        for(int k=0; k<N; k++){
            if(!(i&(1<<C.at(k)))) continue;
            for(auto to : Graph.at(k)) if(i&(1<<C.at(to))) uf.unite(k,to);
        }
        for(int k=0; k<10; k++) if(i&(1<<k)) cost.at(i) += W.at(k);
    }

    int Q; cin >> Q;
    for(int i=0; i<Q; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        long long now = 1e18;
        for(int k=0; k<1024; k++) if(UF.at(k).issame(u,v)) now = min(now,cost.at(k));
        if(now == 1e18) now = -1;
        cout << now << endl;
    }
}
0