CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1628895

Source codeソースコード

#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

int n, m, q;
int d[5010];

struct edge{
   int to, cost;
//    edge(int to, int cost):to(to), cost(cost){}
};
vector<edge> G[5010]; 

struct UF{
   vector<int> par;
   vector<int> sz;
   UF(){}
   UF(int n){
       par.resize(n);
       sz.resize(n, 1);
       rep(i, 0, n) par[i] = i;
   }
   int find(int x){
       if(x == par[x]) return x;
       return par[x] = find(par[x]);
   }
   void unite(int x, int y){
       x = find(x); y = find(y);
       if(x == y) return;
       if(sz[x] < sz[y]) swap(x, y);
       sz[x] += sz[y];
       par[y] = x;
   }
   bool same(int x, int y){
       return find(x) == find(y);
   }
};

vector<pair<int, P> > es; 
// vector<int> path;
int pMAX[4010][4010];
int cost[4010][4010];

void dfs(int now, int pre, int MAX, int root){
    // cout << " " << now << " " << pre << endl;
    // path[now] = pre;
    pMAX[root][now] = MAX;
    // if(now == dest) return;
    rep(i, 0, G[now].size()){
        int next = G[now][i].to;
        if(next == pre) continue;
        // path[next] = now;       
        dfs(next, now, max(MAX, cost[now][next]), root);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    rep(i, 0, m){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        // G[a].push_back(edge{b, c});
        // G[b].push_back(edge{a, c});
        es.push_back(pair<int, P>(c, P(a, b)));
        cost[a][b] = c;
        cost[b][a] = c;
    }
    sort(all(es));
    UF uf(n);
    int sum = 0, cnt = 0;
    rep(i, 0, es.size()){
        int from = es[i].second.first;
        int to = es[i].second.second;
        if(uf.same(from, to) == false){
            uf.unite(from, to);
            sum += es[i].first;
            G[from]. push_back(edge{to, es[i].first});
            G[to]. push_back(edge{from, es[i].first});
        }
    }
    // cout << sum << endl;
    rep(i, 0, n){
        // path.clear(); path.resize(n, -1);
        dfs(i, -1, 0, i);
    }
    cin >> q;
    rep(i, 0, q){
        int s, t;
        cin >> s >> t;
        s--; t--;
        // path.clear(); path.resize(n, -1);
        // dfs(s, -1, t);
        cout << sum - pMAX[s][t] << endl;
        // int MAX = 0;
        // int now = t;
        // while(now != s){
        //     int next = path[now];
        //     chmax(MAX, cost[now][next]);
        //     now = next;
        // }
        // cout << sum - MAX << endl;
        // rep(j, 0, path.size()){
        //     cout << path[j] << " ";
        // }
        // cout << endl;
        // dijkstra(s);
        // cout << d[t] << endl;
    }
}

Submission

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

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt
subtask1 0 / 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 0 / 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 0 / 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 2 ms 2432 KB
sample_2.txt AC 2 ms 2432 KB
subtask_1_1.txt AC 4 ms 6912 KB
subtask_1_10.txt MLE
subtask_1_11.txt AC 2 ms 2432 KB
subtask_1_2.txt AC 519 ms 252404 KB
subtask_1_3.txt MLE
subtask_1_4.txt AC 462 ms 250112 KB
subtask_1_5.txt AC 494 ms 250176 KB
subtask_1_6.txt AC 552 ms 253936 KB
subtask_1_7.txt MLE
subtask_1_8.txt AC 460 ms 250112 KB
subtask_1_9.txt AC 501 ms 250748 KB
subtask_2_1.txt MLE
subtask_2_2.txt MLE
subtask_2_3.txt MLE
subtask_2_4.txt MLE
subtask_2_5.txt AC 458 ms 250112 KB
subtask_2_6.txt AC 515 ms 251640 KB
subtask_2_7.txt AC 560 ms 254704 KB
subtask_2_8.txt MLE
subtask_3_1.txt MLE
subtask_3_2.txt MLE
subtask_3_3.txt AC 663 ms 251520 KB
subtask_3_4.txt AC 694 ms 252156 KB
subtask_3_5.txt MLE
subtask_3_6.txt MLE
subtask_3_7.txt MLE
subtask_3_8.txt MLE