Submission #1662342
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod
int n, m;
int cost[4005][4005];
class UnionFind {
public:
vector<int> parent, rank;
vector<vector<int>> group;
UnionFind(int size) {
group.resize(size);
for (int i = 0; i < size; i++) {
parent.push_back(i);
rank.push_back(0);
group[i].push_back(i);
}
}
int findset(int x) {
return x == parent[x] ? x : parent[x] = findset(parent[x]);
}
void unite(int x, int y, int c) {
x = findset(x); y = findset(y);
if (x == y) return;
if (rank[x] > rank[y]) swap(x, y);
parent[x] = y;
for (auto nodey : group[y]) {
for (auto nodex : group[x]) {
cost[nodey][nodex] = c;
cost[nodex][nodey] = c;
}
}
for (auto ch : group[x]) {
group[y].push_back(ch);
}
if (rank[x] == rank[y]) rank[y] += 1;
}
bool same(int x, int y) {
return findset(x) == findset(y);
}
};
struct edge {ll cost, u, v;};
bool comp(const edge& e1, const edge& e2) {
return e1.cost < e2.cost;
}
vector<edge> es;
ll kruskal(int v, int e, vector<edge> es) {//vは頂点数,eは辺数
sort(all(es), comp); //esは[辺の重み,辺の端点1,辺の端点2]
UnionFind node(v);
ll ret = 0;
for (int i = 0; i < e; i++) {
edge e = es[i];
if (!node.same(e.u, e.v)) {
ret += e.cost;
node.unite(e.u, e.v, e.cost);
}
}
return ret;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
rep(i, m) {
int a, b, c;
cin >> a >> b >> c;
a--; b--;
es.push_back(edge{c, a, b});
}
int total = kruskal(n, m, es);
int q;
cin >> q;
rep(i, q) {
int s, t;
cin >> s >> t;
s--; t--;
cout << total - cost[s][t] << endl;
}
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
roto_37 |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
3362 Byte |
Status |
AC |
Exec Time |
590 ms |
Memory |
146536 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 |
1 ms |
256 KB |
sample_2.txt |
AC |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
2 ms |
2688 KB |
subtask_1_10.txt |
AC |
323 ms |
135276 KB |
subtask_1_11.txt |
AC |
1 ms |
256 KB |
subtask_1_2.txt |
AC |
264 ms |
127732 KB |
subtask_1_3.txt |
AC |
393 ms |
145512 KB |
subtask_1_4.txt |
AC |
220 ms |
126080 KB |
subtask_1_5.txt |
AC |
242 ms |
126016 KB |
subtask_1_6.txt |
AC |
294 ms |
130544 KB |
subtask_1_7.txt |
AC |
394 ms |
145256 KB |
subtask_1_8.txt |
AC |
231 ms |
126080 KB |
subtask_1_9.txt |
AC |
247 ms |
126332 KB |
subtask_2_1.txt |
AC |
396 ms |
146536 KB |
subtask_2_2.txt |
AC |
395 ms |
144872 KB |
subtask_2_3.txt |
AC |
395 ms |
145768 KB |
subtask_2_4.txt |
AC |
391 ms |
144616 KB |
subtask_2_5.txt |
AC |
222 ms |
126080 KB |
subtask_2_6.txt |
AC |
250 ms |
126712 KB |
subtask_2_7.txt |
AC |
281 ms |
130544 KB |
subtask_2_8.txt |
AC |
392 ms |
146152 KB |
subtask_3_1.txt |
AC |
566 ms |
146280 KB |
subtask_3_2.txt |
AC |
590 ms |
145896 KB |
subtask_3_3.txt |
AC |
413 ms |
127068 KB |
subtask_3_4.txt |
AC |
420 ms |
126992 KB |
subtask_3_5.txt |
AC |
486 ms |
135276 KB |
subtask_3_6.txt |
AC |
523 ms |
140648 KB |
subtask_3_7.txt |
AC |
566 ms |
145768 KB |
subtask_3_8.txt |
AC |
564 ms |
146024 KB |