CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1151768

Source codeソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, ll> P;

vector< vector<P> > G;

struct Union_Find {
    //各要素が属する集合の代表(根)を管理する
    //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい
    vector<int> data;
    
    Union_Find(int size) : data(size, -1) {}
    bool Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        bool is_union = (x != y);
        if (is_union) {
            if (data[x] > data[y]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return is_union;
    }
    int Find(int x) {
        if (data[x] < 0) { //要素xが根である
            return x;
        } else {
            data[x] = Find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される
            return data[x];
        }
    }
    bool same(int x, int y) {
        return Find(x) == Find(y);
    }
    int size(int x) {
        return -data[Find(x)];
    }
};

struct Edge {
    int u, v;
    ll cost;
    bool operator<(const Edge& e) const {
        return cost < e.cost;
    }
}; 

struct Graph {
    int n; //頂点数
    vector<Edge> es; //辺集合
    
    ll kruskal() {
        sort(es.begin(), es.end());
        Union_Find uf(n);
        ll min_cost = 0;
        for(int i = 0; i < (int)es.size(); i++) {
            Edge e = es[i];
            if (!uf.same(e.u, e.v)) {
                min_cost += e.cost;
                uf.Union(e.u, e.v);
                G[e.u].emplace_back(e.v, e.cost);
                G[e.v].emplace_back(e.u, e.cost);
            }
        }
        return min_cost;
    }
};

Graph input() {
   Graph g;
   int m;
   cin >> g.n >> m;
   g.es = vector<Edge>(m);
   for(int i = 0; i < m; i++) {
        cin >> g.es[i].u >> g.es[i].v >> g.es[i].cost;
        g.es[i].u--;
        g.es[i].v--;
   }
   return g;
}

void dfs(int cur, int par, vector<ll>& d) {
    for (P nex : G[cur]) {
        if (nex.first == par) continue;
        d[nex.first] = max(d[cur], nex.second);
        dfs(nex.first, cur, d);
    }
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	Graph g = input();
    G.resize(g.n);
    ll sum = g.kruskal();
    vector< vector<ll> > maxc(g.n, vector<ll>(g.n, 0));
    for (int i = 0; i < g.n; i++) {
        dfs(i, -1, maxc[i]);
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        s--;
        t--;
        cout << sum - maxc[s][t] << endl;
    }
	return 0;
}

Submission

Task問題 A - グラフ / Graph
User nameユーザ名 fine
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 2728 Byte
File nameファイル名
Exec time実行時間 779 ms
Memory usageメモリ使用量 133248 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt
subtask1 200 / 200 sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt
subtask2 300 / 300 sample_1.txt,sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt
All 200 / 200 sample_1.txt,sample_2.txt,sample_1.txt,sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_3_1.txt,subtask_3_2.txt,subtask_3_3.txt,subtask_3_4.txt,subtask_3_5.txt,subtask_3_6.txt,subtask_3_7.txt,subtask_3_8.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
subtask_1_1.txt AC 2 ms 384 KB
subtask_1_10.txt AC 531 ms 128896 KB
subtask_1_11.txt AC 1 ms 256 KB
subtask_1_2.txt AC 480 ms 126336 KB
subtask_1_3.txt AC 597 ms 131968 KB
subtask_1_4.txt AC 445 ms 125824 KB
subtask_1_5.txt AC 472 ms 125824 KB
subtask_1_6.txt AC 502 ms 127360 KB
subtask_1_7.txt AC 616 ms 131968 KB
subtask_1_8.txt AC 439 ms 125824 KB
subtask_1_9.txt AC 479 ms 125952 KB
subtask_2_1.txt AC 604 ms 132096 KB
subtask_2_2.txt AC 603 ms 132096 KB
subtask_2_3.txt AC 616 ms 132096 KB
subtask_2_4.txt AC 605 ms 132096 KB
subtask_2_5.txt AC 441 ms 125824 KB
subtask_2_6.txt AC 484 ms 126080 KB
subtask_2_7.txt AC 510 ms 127360 KB
subtask_2_8.txt AC 610 ms 132096 KB
subtask_3_1.txt AC 776 ms 133248 KB
subtask_3_2.txt AC 775 ms 133248 KB
subtask_3_3.txt AC 623 ms 127232 KB
subtask_3_4.txt AC 661 ms 127232 KB
subtask_3_5.txt AC 722 ms 130048 KB
subtask_3_6.txt AC 748 ms 131584 KB
subtask_3_7.txt AC 777 ms 133248 KB
subtask_3_8.txt AC 779 ms 133248 KB