Submission #1628892


Source Code Expand

#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 Info

Submission Time
Task A - Graph
User treeone
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3064 Byte
Status MLE
Exec Time 876 ms
Memory 263912 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 300 0 / 200
Status
AC × 2
AC × 9
MLE × 3
AC × 13
MLE × 8
AC × 17
MLE × 14
Set Name Test Cases
Sample sample_1.txt, sample_2.txt
subtask1 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 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 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
Case Name Status Exec Time Memory
sample_1.txt AC 2 ms 2432 KB
sample_2.txt AC 2 ms 2432 KB
subtask_1_1.txt AC 3 ms 6912 KB
subtask_1_10.txt MLE 607 ms 256620 KB
subtask_1_11.txt AC 2 ms 2432 KB
subtask_1_2.txt AC 527 ms 252404 KB
subtask_1_3.txt MLE 695 ms 262376 KB
subtask_1_4.txt AC 479 ms 250240 KB
subtask_1_5.txt AC 521 ms 250176 KB
subtask_1_6.txt AC 561 ms 254320 KB
subtask_1_7.txt MLE 692 ms 261224 KB
subtask_1_8.txt AC 471 ms 250112 KB
subtask_1_9.txt AC 519 ms 250748 KB
subtask_2_1.txt MLE 699 ms 261480 KB
subtask_2_2.txt MLE 695 ms 262504 KB
subtask_2_3.txt MLE 703 ms 261480 KB
subtask_2_4.txt MLE 706 ms 262376 KB
subtask_2_5.txt AC 473 ms 250240 KB
subtask_2_6.txt AC 529 ms 251640 KB
subtask_2_7.txt AC 569 ms 254064 KB
subtask_2_8.txt MLE 695 ms 262376 KB
subtask_3_1.txt MLE 876 ms 263912 KB
subtask_3_2.txt MLE 863 ms 263784 KB
subtask_3_3.txt AC 649 ms 251520 KB
subtask_3_4.txt AC 697 ms 252028 KB
subtask_3_5.txt MLE 770 ms 258924 KB
subtask_3_6.txt MLE 822 ms 260968 KB
subtask_3_7.txt MLE 855 ms 262376 KB
subtask_3_8.txt MLE 857 ms 263784 KB