Submission #1053927
Source Code Expand
#include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; class UnionFind { private: unsigned size_; std::vector<unsigned> par, rank; public: UnionFind() : size_(0), par(std::vector<unsigned>()), rank(std::vector<unsigned>()) {}; UnionFind(unsigned size__) : size_(size__) { par.resize(size_); rank.resize(size_); for (unsigned i = 0; i < size_; i++) par[i] = i, rank[i] = 0; } unsigned size() { return size_; } unsigned root(unsigned x) { return par[x] == x ? x : par[x] = root(par[x]); } bool same(unsigned x, unsigned y) { return root(x) == root(y); } void unite(unsigned x, unsigned y) { x = root(x), y = root(y); if (x == y) return; if (rank[x] < rank[y]) par[x] = y; else if (rank[x] == rank[y]) par[y] = x, rank[x]++; else par[y] = x; } bool operator==(const UnionFind &u) { return par == u.par; } bool operator!=(const UnionFind &u) { return par != u.par; } }; int n, m, q, a[400000], b[400000], c[400000], dist[5000]; vector<pair<int, int>>vec; vector<pair<int, int>>x[5000]; int query(int r1, int r2) { fill(dist + 1, dist + n + 1, 1299999999); queue<int>Q; Q.push(r1); dist[r1] = 0; while (!Q.empty()) { int a1 = Q.front(); Q.pop(); if (a1 == r2)return dist[a1]; for (int i = 0; i < x[a1].size(); i++) { if (dist[x[a1][i].first] == 1299999999) { dist[x[a1][i].first] = max(dist[a1], x[a1][i].second); Q.push(x[a1][i].first); } } } return dist[r2]; } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { cin >> a[i] >> b[i] >> c[i]; vec.push_back(make_pair(c[i], i)); } sort(vec.begin(), vec.end()); UnionFind UF(n + 1); long long sum = 0; for (int i = 0; i < vec.size(); i++) { int to = vec[i].second; if (UF.same(a[to], b[to]) == false) { UF.unite(a[to], b[to]); sum += c[to]; x[a[to]].push_back(make_pair(b[to], c[to])); x[b[to]].push_back(make_pair(a[to], c[to])); } } cin >> q; for (int i = 0; i < q; i++) { int p1, p2; cin >> p1 >> p2; cout << sum - query(p1, p2) << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | E869120 |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2091 Byte |
Status | TLE |
Exec Time | 3155 ms |
Memory | 8940 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 300 / 300 | 0 / 200 | ||||||||||
Status |
|
|
|
|
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 | 384 KB |
sample_2.txt | AC | 3 ms | 512 KB |
subtask_1_1.txt | AC | 4 ms | 384 KB |
subtask_1_10.txt | AC | 200 ms | 4464 KB |
subtask_1_11.txt | AC | 3 ms | 384 KB |
subtask_1_2.txt | AC | 42 ms | 1404 KB |
subtask_1_3.txt | AC | 399 ms | 8428 KB |
subtask_1_4.txt | AC | 7 ms | 640 KB |
subtask_1_5.txt | AC | 8 ms | 640 KB |
subtask_1_6.txt | AC | 100 ms | 2548 KB |
subtask_1_7.txt | AC | 402 ms | 8428 KB |
subtask_1_8.txt | AC | 7 ms | 640 KB |
subtask_1_9.txt | AC | 13 ms | 768 KB |
subtask_2_1.txt | AC | 575 ms | 8428 KB |
subtask_2_2.txt | AC | 575 ms | 8428 KB |
subtask_2_3.txt | AC | 576 ms | 8428 KB |
subtask_2_4.txt | AC | 579 ms | 8428 KB |
subtask_2_5.txt | AC | 190 ms | 640 KB |
subtask_2_6.txt | AC | 199 ms | 1020 KB |
subtask_2_7.txt | AC | 280 ms | 2676 KB |
subtask_2_8.txt | AC | 573 ms | 8428 KB |
subtask_3_1.txt | TLE | 3154 ms | 8940 KB |
subtask_3_2.txt | TLE | 3154 ms | 8940 KB |
subtask_3_3.txt | TLE | 3154 ms | 1408 KB |
subtask_3_4.txt | TLE | 3154 ms | 1408 KB |
subtask_3_5.txt | TLE | 3154 ms | 5104 KB |
subtask_3_6.txt | TLE | 3154 ms | 7664 KB |
subtask_3_7.txt | TLE | 3154 ms | 8940 KB |
subtask_3_8.txt | TLE | 3155 ms | 8940 KB |