Submission #2558711


Source Code Expand

// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

struct Edge {
    int from, to, cost;
    Edge(int t, int c) : to(t), cost(c) {}
    Edge(int f, int t, int c) : from(f), to(t), cost(c) {}
    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
};

const int MAXN = 4010;
struct UnionFind {
    int node[MAXN];
    UnionFind() {
        memset(node, -1, sizeof(node));
    }
    int find(int x) {
        return node[x] < 0 ? x : node[x] = find(node[x]);
    }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return false;
        node[x] += node[y];
        node[y] = x;
        return true;
    }
};

using Graph = vector< vector<Edge> >;
int max_edge[MAXN][MAXN];

void dfs(Graph &G, int cur, int par, int orig) {
    int prev_max = (par < 0 ? 0 : max_edge[orig][par]);
    for(auto e : G[cur]) {
        if(e.to == par) continue;
        chmax(max_edge[orig][e.to], max(prev_max, e.cost));
        dfs(G, e.to, cur, orig);
    }
}
 
UnionFind uf;
signed main() {
    int N, M; cin >> N >> M;
    
    vector<Edge> edges;
    for(int i=0; i<M; i++) {
        int u, v, cost; cin >> u >> v >> cost;
        u--; v--;
        edges.emplace_back(u, v, cost);
    }
    sort(edges.begin(), edges.end());

    int sum = 0;
    Graph MST(N);
    for(int i=0; i<M; i++) {
        Edge e = edges[i];
        if(uf.unite(e.from, e.to)) {
            MST[e.from].emplace_back(e.from, e.to  , e.cost);
            MST[e.to  ].emplace_back(e.to,   e.from, e.cost);
            sum += e.cost;
        }
    }

    for(int i=0; i<N; i++) dfs(MST, i, -1, i);

    /*
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            printf("max_edge[%lld][%lld] = %lld\n", i+1, j+1, max_edge[i][j]);
        }
    }
    */

    int Q; cin >> Q;
    for(int i=0; i<Q; i++) {
        int s, t; cin >> s >> t;
        s--; t--;
        // printf("max_edge = %lld\n", max_edge[s][t]);
        cout << sum - max(max_edge[s][t], max_edge[t][s]) << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task A - Graph
User tsutaj
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3172 Byte
Status WA
Exec Time 1070 ms
Memory 137832 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
WA × 3
AC × 10
WA × 11
AC × 12
WA × 19
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 384 KB
sample_2.txt AC 1 ms 256 KB
subtask_1_1.txt WA 3 ms 2688 KB
subtask_1_10.txt AC 633 ms 131180 KB
subtask_1_11.txt AC 1 ms 256 KB
subtask_1_2.txt AC 485 ms 126836 KB
subtask_1_3.txt WA 831 ms 137320 KB
subtask_1_4.txt AC 403 ms 126080 KB
subtask_1_5.txt AC 445 ms 126016 KB
subtask_1_6.txt AC 544 ms 128240 KB
subtask_1_7.txt AC 827 ms 136680 KB
subtask_1_8.txt AC 393 ms 126080 KB
subtask_1_9.txt WA 454 ms 126204 KB
subtask_2_1.txt WA 836 ms 135400 KB
subtask_2_2.txt WA 827 ms 136552 KB
subtask_2_3.txt WA 833 ms 135400 KB
subtask_2_4.txt WA 835 ms 136296 KB
subtask_2_5.txt WA 394 ms 126080 KB
subtask_2_6.txt WA 487 ms 126456 KB
subtask_2_7.txt WA 553 ms 128368 KB
subtask_2_8.txt WA 830 ms 136552 KB
subtask_3_1.txt WA 1042 ms 137320 KB
subtask_3_2.txt WA 1043 ms 137448 KB
subtask_3_3.txt WA 614 ms 127360 KB
subtask_3_4.txt WA 691 ms 127484 KB
subtask_3_5.txt WA 861 ms 131820 KB
subtask_3_6.txt WA 948 ms 135272 KB
subtask_3_7.txt WA 1045 ms 136552 KB
subtask_3_8.txt WA 1070 ms 137832 KB