Submission #1175833
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv=vector<vector< T > >;
class UF {
private:
vector<int> data; // parent or size
vector<int> next;
vector<int> last;
void init(int n) {
data.assign(n, -1);
next.assign(n, -1);
last.resize(n);
for (int i = 0; i < n; ++i) {
last[i] = i;
}
}
public:
UF() {}
UF(int n) {
init(n);
}
int root(int x) {
if (data[x] < 0) return x;
return data[x] = root(data[x]);
}
bool unite(int x, int y) {
x = root(x);
y = root(y);
if (x == y) return false;
if (data[x] > data[y]) swap(x, y); // data[x] and data[y] are negative.
data[x] += data[y];
data[y] = x;
next[last[x]] = y;
last[x] = last[y];
return true;
}
int size(int x) {
return -data[root(x)];
}
bool same(int x, int y) {
return root(x) == root(y);
}
int get_next(int x) {
return next[x];
}
};
int main() {
int n, m;
scanf("%d%d", &n, &m);
vvi edge(m, vi(3));
rep (i, m) {
scanf("%d%d%d", &edge[i][1], &edge[i][2], &edge[i][0]);
edge[i][1] -= 1; edge[i][2] -= 1;
}
sort(all(edge));
UF uf(n);
vvi maxcost(n, vi(n));
ll cost = 0;
cost += edge[0][0];
uf.unite(edge[0][1], edge[0][2]);
maxcost[edge[0][1]][edge[0][2]] = maxcost[edge[0][2]][edge[0][1]] = edge[0][0];
FOR (i, 1, m) {
int x = edge[i][1];
int y = edge[i][2];
if (!(uf.same(x, y))) {
cost += edge[i][0];
for (int j = uf.root(x); j != -1; j = uf.get_next(j)) {
for (int k = uf.root(y); k != -1; k = uf.get_next(k)) {
maxcost[j][k] = maxcost[k][j] = edge[i][0];
}
}
uf.unite(x, y);
}
}
int q;
cin >> q;
vll ans(q, 0);
rep (j, q) {
int s, t;
cin >> s >> t;
s -= 1; t -= 1;
ans[j] = cost - maxcost[s][t];
}
rep (i, q) {
printf("%lld\n", ans[i]);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
tspcx |
Language |
C++14 (Clang 3.8.0) |
Score |
700 |
Code Size |
2746 Byte |
Status |
AC |
Exec Time |
730 ms |
Memory |
86784 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, 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 |
6 ms |
888 KB |
sample_2.txt |
AC |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
2 ms |
384 KB |
subtask_1_10.txt |
AC |
441 ms |
73856 KB |
subtask_1_11.txt |
AC |
1 ms |
256 KB |
subtask_1_2.txt |
AC |
356 ms |
65152 KB |
subtask_1_3.txt |
AC |
546 ms |
84864 KB |
subtask_1_4.txt |
AC |
274 ms |
63232 KB |
subtask_1_5.txt |
AC |
270 ms |
63232 KB |
subtask_1_6.txt |
AC |
400 ms |
68480 KB |
subtask_1_7.txt |
AC |
587 ms |
84864 KB |
subtask_1_8.txt |
AC |
279 ms |
63232 KB |
subtask_1_9.txt |
AC |
313 ms |
63488 KB |
subtask_2_1.txt |
AC |
549 ms |
84864 KB |
subtask_2_2.txt |
AC |
570 ms |
84864 KB |
subtask_2_3.txt |
AC |
539 ms |
84864 KB |
subtask_2_4.txt |
AC |
580 ms |
84864 KB |
subtask_2_5.txt |
AC |
276 ms |
63232 KB |
subtask_2_6.txt |
AC |
338 ms |
64128 KB |
subtask_2_7.txt |
AC |
388 ms |
68480 KB |
subtask_2_8.txt |
AC |
564 ms |
84864 KB |
subtask_3_1.txt |
AC |
698 ms |
86784 KB |
subtask_3_2.txt |
AC |
686 ms |
86784 KB |
subtask_3_3.txt |
AC |
425 ms |
65280 KB |
subtask_3_4.txt |
AC |
455 ms |
65536 KB |
subtask_3_5.txt |
AC |
576 ms |
75904 KB |
subtask_3_6.txt |
AC |
669 ms |
81280 KB |
subtask_3_7.txt |
AC |
730 ms |
86784 KB |
subtask_3_8.txt |
AC |
704 ms |
86784 KB |