Submission #1026555


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

class union_find{
	private:
	vector<int> parent,rank,gs;
    int size;
	public:
    int count_group;
    union_find()=default;
    union_find(int n){ init(n); }
    void init(int n){
		size=n;
		count_group=n;
		parent.resize(size);
		rank.assign(size,0);
        gs.assign(size,1);
		for(int i=0; i<size; ++i) parent[i]=i;
	}
	int find(int x){
		if(parent[x]==x) return x;
		else return parent[x]=find(parent[x]);
	}
	void unite(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y]){
			parent[x]=y;
            gs[y]+=gs[x];
		} else {
			parent[y]=x;
            gs[x]+=gs[y];
			if(rank[x]==rank[y]) ++rank[x];
		}
		--count_group;
	}
	bool is_same_group(int x,int y){
		return find(x)==find(y);
	}
    int group_size(int x){
        return gs[find(x)];
    };
};

struct edge{
    int from,to,cost;
    bool operator<(const edge& other)const{
        return cost<other.cost;
    }
};

void solve(){
    int n,m;
    cin >> n >> m;
    vector<edge> edges;
    vector<unordered_map<int,int>> cost(n);
    rep(i,0,m){
        int a,b,c;
        cin >> a >> b >> c;
        --a;
        --b;
        edges.push_back(edge({a,b,c}));
    }
    sort(edges.begin(),edges.end());

    int q;
    cin >> q;
    if(int64_t(m)*q>10000000) return;
    rep(i,0,q){
        int s,t;
        cin >> s >> t;
        --s;
        --t;

        union_find uf(n);
        uf.unite(s,t);
        int sum=0;
        for(edge &edge:edges){
            int a=edge.from,b=edge.to;
            int x=uf.find(s),y=uf.find(t);
            if(uf.is_same_group(a,b)) continue;
            uf.unite(a,b);
            sum+=edge.cost;
        }
        cout << sum << endl;
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}

Submission Info

Submission Time
Task A - Graph
User walkre
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2481 Byte
Status WA
Exec Time 146 ms
Memory 6768 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 300 0 / 200
Status
AC × 2
AC × 2
WA × 10
AC × 3
WA × 18
AC × 3
WA × 26
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, 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 3 ms 256 KB
sample_2.txt AC 3 ms 256 KB
subtask_1_1.txt WA 3 ms 256 KB
subtask_1_10.txt WA 72 ms 3700 KB
subtask_1_11.txt AC 3 ms 384 KB
subtask_1_2.txt WA 17 ms 1404 KB
subtask_1_3.txt WA 145 ms 6768 KB
subtask_1_4.txt WA 4 ms 640 KB
subtask_1_5.txt WA 5 ms 640 KB
subtask_1_6.txt WA 37 ms 2168 KB
subtask_1_7.txt WA 143 ms 6768 KB
subtask_1_8.txt WA 4 ms 640 KB
subtask_1_9.txt WA 6 ms 768 KB
subtask_2_1.txt WA 141 ms 6768 KB
subtask_2_2.txt WA 142 ms 6768 KB
subtask_2_3.txt WA 142 ms 6768 KB
subtask_2_4.txt WA 141 ms 6768 KB
subtask_2_5.txt WA 4 ms 512 KB
subtask_2_6.txt WA 10 ms 960 KB
subtask_2_7.txt WA 37 ms 2168 KB
subtask_2_8.txt WA 141 ms 6768 KB
subtask_3_1.txt WA 141 ms 6768 KB
subtask_3_2.txt WA 141 ms 6768 KB
subtask_3_3.txt WA 4 ms 512 KB
subtask_3_4.txt WA 6 ms 768 KB
subtask_3_5.txt WA 72 ms 3700 KB
subtask_3_6.txt WA 111 ms 6768 KB
subtask_3_7.txt WA 146 ms 6768 KB
subtask_3_8.txt WA 141 ms 6768 KB