CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1476096

Source codeソースコード

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

struct union_find{
    VI par;

    void init(int n){
        par.resize(n);
        REP(i,n) par[i] = i;
    }

    int find(int x){
        if (par[x] == x) return x;
        else return par[x] = find(par[x]);
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    void merge(int x, int y){
        x = find(x);
        y = find(y);
        if (x == y) return;
        par[x] = y;
    }
};

struct edge{ int u, v, cost; };
VL em[4000], um[4000];
int ma[4000][4000];

bool comp(const edge &e1, const edge &e2){
    return e1.cost < e2.cost;
}

ll kruskal(vector<edge> &es, int n){
    sort(es.begin(), es.end(), comp);
    union_find uf;
    uf.init(n);
    ll res = 0;
    REP(i,es.size()){
        edge e = es[i];
        if (!uf.same(e.u, e.v)){
            uf.merge(e.u, e.v);
            res += e.cost;
            em[e.u].push_back(e.v);
            um[e.u].push_back(e.cost);
            em[e.v].push_back(e.u);
            um[e.v].push_back(e.cost);
        }
    }
    return res;
}

void dfs(int now, int past, ll x, int s){
    ma[s][now] = x;
    REP(i,em[now].size()){
        if (em[now][i] == past) continue;
        dfs(em[now][i], now, max(x, um[now][i]), s);
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<edge> es;
    while(m--){
        edge eg;
        scanf("%d %d %d", &eg.u, &eg.v, &eg.cost);
        eg.u--;
        eg.v--;
        es.push_back(eg);
    }

    ll sum = kruskal(es, n);

    REP(i,n) dfs(i, -1, 0, i);

    int q;
    cin >> q;
    while (q--){
        int s, t;
        scanf("%d %d", &s, &t);
        s--;
        t--;
        printf("%lld\n", sum - ma[s][t]);
    }

    return 0;
}

Submission

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

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:94:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &eg.u, &eg.v, &eg.cost);
^
./Main.cpp:108:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &s, &t);
^

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 384 KB
sample_2.txt AC 1 ms 384 KB
subtask_1_1.txt AC 2 ms 896 KB
subtask_1_10.txt AC 547 ms 65520 KB
subtask_1_11.txt AC 1 ms 384 KB
subtask_1_2.txt AC 487 ms 63736 KB
subtask_1_3.txt AC 620 ms 67948 KB
subtask_1_4.txt AC 422 ms 63232 KB
subtask_1_5.txt AC 470 ms 63360 KB
subtask_1_6.txt AC 511 ms 64372 KB
subtask_1_7.txt AC 628 ms 69228 KB
subtask_1_8.txt AC 428 ms 63232 KB
subtask_1_9.txt AC 479 ms 63304 KB
subtask_2_1.txt AC 621 ms 68076 KB
subtask_2_2.txt AC 616 ms 68588 KB
subtask_2_3.txt AC 626 ms 68716 KB
subtask_2_4.txt AC 630 ms 68972 KB
subtask_2_5.txt AC 414 ms 63360 KB
subtask_2_6.txt AC 489 ms 63484 KB
subtask_2_7.txt AC 514 ms 64500 KB
subtask_2_8.txt AC 617 ms 69100 KB
subtask_3_1.txt AC 653 ms 69228 KB
subtask_3_2.txt AC 655 ms 70380 KB
subtask_3_3.txt AC 453 ms 64640 KB
subtask_3_4.txt AC 515 ms 64576 KB
subtask_3_5.txt AC 580 ms 67184 KB
subtask_3_6.txt AC 613 ms 68588 KB
subtask_3_7.txt AC 650 ms 70508 KB
subtask_3_8.txt AC 651 ms 70252 KB