Submission #1628887


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;

void dfs(int now, int pre, int dest){
    // cout << " " << now << " " << pre << endl;
    path[now] = pre;
    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, dest);
    }
}

int cost[4010][4010];

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;
    cin >> q;
    rep(i, 0, q){
        int s, t;
        cin >> s >> t;
        s--; t--;
        path.clear(); path.resize(n, -1);
        dfs(s, -1, t);
        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 500
Code Size 2807 Byte
Status TLE
Exec Time 3156 ms
Memory 140012 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 200 / 200 300 / 300 0 / 200
Status
AC × 2
AC × 12
AC × 21
AC × 23
TLE × 8
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 1 ms 384 KB
sample_2.txt AC 1 ms 384 KB
subtask_1_1.txt AC 2 ms 2816 KB
subtask_1_10.txt AC 113 ms 133232 KB
subtask_1_11.txt AC 1 ms 384 KB
subtask_1_2.txt AC 44 ms 126968 KB
subtask_1_3.txt AC 205 ms 138988 KB
subtask_1_4.txt AC 28 ms 124288 KB
subtask_1_5.txt AC 28 ms 124352 KB
subtask_1_6.txt AC 70 ms 128884 KB
subtask_1_7.txt AC 202 ms 140012 KB
subtask_1_8.txt AC 28 ms 124160 KB
subtask_1_9.txt AC 30 ms 124924 KB
subtask_2_1.txt AC 533 ms 138604 KB
subtask_2_2.txt AC 530 ms 139244 KB
subtask_2_3.txt AC 525 ms 139500 KB
subtask_2_4.txt AC 527 ms 138860 KB
subtask_2_5.txt AC 326 ms 124416 KB
subtask_2_6.txt AC 371 ms 125944 KB
subtask_2_7.txt AC 392 ms 129908 KB
subtask_2_8.txt AC 524 ms 139372 KB
subtask_3_1.txt TLE 3156 ms 139372 KB
subtask_3_2.txt TLE 3156 ms 139372 KB
subtask_3_3.txt TLE 3156 ms 124800 KB
subtask_3_4.txt TLE 3156 ms 125308 KB
subtask_3_5.txt TLE 3156 ms 132592 KB
subtask_3_6.txt TLE 3156 ms 139884 KB
subtask_3_7.txt TLE 3156 ms 138732 KB
subtask_3_8.txt TLE 3156 ms 138220 KB