Submission #996838
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define VI vector<int>
void dfs(int node, int f, vector<VI> &G, vector<VI> &C, VI &d, int val) {
d[node] = val;
for(int i = 0; i < int(G[node].size()); ++i) {
int temp = G[node][i];
if(temp == f)
continue;
dfs(temp, node, G, C, d, max(val, C[node][i]));
}
}
int main() {
//ifstream cin("testA.in");
int n, m; cin >> n >> m;
vector<int> a(m, 0), b(m, 0), c(m, 0);
vector<pair<int, int>> edges;
for(int i = 0; i < m; ++i) {
cin >> a[i] >> b[i] >> c[i];
a[i]--;
b[i]--;
}
for(int i = 0; i < m; ++i) {
edges.push_back({c[i], i});
}
sort(edges.begin(), edges.end());
vector<int> dad(n, 0), sz(n, 0);
for(int i = 0; i < n; ++i)
dad[i] = i;
auto f = [&] (int x) {
int root = x;
int steps = 0;
while(root != dad[root]) {
root = dad[root];
++steps;
}
while(x != root) {
int temp = dad[x];
dad[x] = root;
x = temp;
}
return root;
};
auto unite = [&] (int a, int b) {
dad[a] = b;
};
vector<vector<int>> G(n), C(n);
long long ans = 0;
for(auto edge : edges) {
int x = a[edge.second];
int y = b[edge.second];
if(f(x) != f(y)) {
ans += edge.first;
unite(f(x), f(y));
G[x].push_back(y);
G[y].push_back(x);
C[x].push_back(edge.first);
C[y].push_back(edge.first);
}
}
vector<vector<int>> d(n, vector<int> (n, 0));
for(int i = 0; i < n; ++i) {
int now = 0;
dfs(i, -1, G, C, d[i], now);
}
int q; cin >> q;
for(int i = 0; i < q; ++i) {
int x, y; cin >> x >> y;
x--;y--;
cout << ans - d[x][y] << "\n";
}
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
mcalancea |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2001 Byte |
Status |
AC |
Exec Time |
1436 ms |
Memory |
72428 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
200 / 200 |
300 / 300 |
200 / 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 |
256 KB |
sample_2.txt |
AC |
3 ms |
256 KB |
subtask_1_1.txt |
AC |
4 ms |
256 KB |
subtask_1_10.txt |
AC |
734 ms |
67312 KB |
subtask_1_11.txt |
AC |
3 ms |
256 KB |
subtask_1_2.txt |
AC |
582 ms |
64120 KB |
subtask_1_3.txt |
AC |
946 ms |
71148 KB |
subtask_1_4.txt |
AC |
501 ms |
63488 KB |
subtask_1_5.txt |
AC |
539 ms |
63488 KB |
subtask_1_6.txt |
AC |
645 ms |
65396 KB |
subtask_1_7.txt |
AC |
949 ms |
71148 KB |
subtask_1_8.txt |
AC |
501 ms |
63488 KB |
subtask_1_9.txt |
AC |
552 ms |
63616 KB |
subtask_2_1.txt |
AC |
957 ms |
71276 KB |
subtask_2_2.txt |
AC |
958 ms |
71276 KB |
subtask_2_3.txt |
AC |
955 ms |
71276 KB |
subtask_2_4.txt |
AC |
958 ms |
71276 KB |
subtask_2_5.txt |
AC |
514 ms |
63488 KB |
subtask_2_6.txt |
AC |
581 ms |
63868 KB |
subtask_2_7.txt |
AC |
658 ms |
65396 KB |
subtask_2_8.txt |
AC |
956 ms |
71276 KB |
subtask_3_1.txt |
AC |
1422 ms |
72428 KB |
subtask_3_2.txt |
AC |
1427 ms |
72428 KB |
subtask_3_3.txt |
AC |
1009 ms |
64768 KB |
subtask_3_4.txt |
AC |
1070 ms |
64896 KB |
subtask_3_5.txt |
AC |
1226 ms |
68464 KB |
subtask_3_6.txt |
AC |
1330 ms |
70380 KB |
subtask_3_7.txt |
AC |
1424 ms |
72428 KB |
subtask_3_8.txt |
AC |
1436 ms |
72428 KB |