Submission #1005188
Source Code Expand
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#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 unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
// cout pair
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
s << p.first << " " << p.second << "\n"; return s;
}
// cout vector<pair>
template<typename T1, typename T2> ostream& operator<<(ostream& s, const vector<pair<T1, T2> >& vp) {
int len = vp.size(); s << "\n";
for (int i = 0; i < len; ++i) { s << vp[i]; }
s << "\n"; return s;
}
// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
int len = v.size(); s << "\n";
for (int i = 0; i < len; ++i) {
s << v[i]; if (i < len - 1) s << "\t";
}
s << "\n"; return s;
}
// cout deque
template<typename T> ostream& operator<<(ostream& s, const deque<T>& v) {
int len = v.size(); s << "\n";
for (int i = 0; i < len; ++i) {
s << v[i]; if (i < len - 1) s << "\t";
}
s << "\n"; return s;
}
// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
int len = vv.size();
for (int i = 0; i < len; ++i) { s << vv[i]; }
return s;
}
// cout 2-dimentional deque
template<typename T> ostream& operator<<(ostream& s, const deque< deque<T> >& vv) {
int len = vv.size();
for (int i = 0; i < len; ++i) { s << vv[i]; }
return s;
}
struct UF {
vector<int> par; // parent
vector<int> sizes;
vector<int> next;
vector<int> last;
UF(int n) : par(n), sizes(n, 1), next(n, -1), last(n) {
for (int i = 0; i < n; ++i) {
par[i] = i;
last[i] = i;
}
}
int root(int x) {
if (x == par[x]) return x;
return par[x] = root(par[x]);
}
void unite(int x, int y) {
x = root(x);
y = root(y);
if (x == y) {
return;
}
if (sizes[x] < sizes[y]) {
swap(x, y);
}
par[y] = x;
sizes[x] += sizes[y];
sizes[y] = 0;
next[last[x]] = y;
last[x] = last[y];
}
bool same(int x, int y) {
return root(x) == root(y);
}
int size(int x) {
return sizes[root(x)];
}
};
int main() {
int n, m;
cin >> n >> m;
vv<vi> g(n);
rep (i, m) {
int a, b, c;
cin >> a >> b >> c;
a -= 1; b -= 1;
g[a].pb({c, b, a}); // 0:cost, 1:opponent, 2:self
g[b].pb({c, a, b});
}
rep (i, n) {
sort(all(g[i]));
}
UF uf(n);
vvi maxcost(n, vi(n));
ll cost = 0;
set<vi> cand;
cand.insert(all(g[0]));
while (uf.size(0) < n) {
vi edge = *begin(cand);
cand.erase(begin(cand));
if (uf.same(edge[1], edge[2])) {
continue;
}
assert(uf.same(0, edge[2]));
assert(!uf.same(0, edge[1]));
for (int i = uf.root(edge[2]); i != -1; i = uf.next[i]) {
assert(!uf.same(i, edge[1]));
assert(uf.same(0, i));
maxcost[i][edge[1]] = maxcost[edge[1]][i] = edge[0];
}
cost += edge[0];
uf.unite(edge[1], edge[2]);
cand.insert(all(g[edge[1]]));
}
int q;
cin >> q;
vll ans(q, 0);
rep (i, q) {
int s, t;
cin >> s >> t;
s -= 1; t -= 1;
ans[i] = 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 |
0 |
Code Size |
4099 Byte |
Status |
WA |
Exec Time |
3158 ms |
Memory |
187136 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
0 / 200 |
0 / 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 |
256 KB |
sample_2.txt |
AC |
3 ms |
256 KB |
subtask_1_1.txt |
WA |
6 ms |
640 KB |
subtask_1_10.txt |
AC |
1936 ms |
123264 KB |
subtask_1_11.txt |
AC |
3 ms |
256 KB |
subtask_1_2.txt |
WA |
935 ms |
74496 KB |
subtask_1_3.txt |
TLE |
3080 ms |
185216 KB |
subtask_1_4.txt |
WA |
725 ms |
63616 KB |
subtask_1_5.txt |
WA |
681 ms |
63872 KB |
subtask_1_6.txt |
AC |
1205 ms |
92672 KB |
subtask_1_7.txt |
TLE |
3008 ms |
185088 KB |
subtask_1_8.txt |
WA |
660 ms |
63616 KB |
subtask_1_9.txt |
WA |
714 ms |
65280 KB |
subtask_2_1.txt |
WA |
2998 ms |
185216 KB |
subtask_2_2.txt |
WA |
2985 ms |
185216 KB |
subtask_2_3.txt |
TLE |
3001 ms |
185216 KB |
subtask_2_4.txt |
TLE |
3076 ms |
185216 KB |
subtask_2_5.txt |
WA |
712 ms |
63616 KB |
subtask_2_6.txt |
WA |
818 ms |
68352 KB |
subtask_2_7.txt |
WA |
1268 ms |
92672 KB |
subtask_2_8.txt |
WA |
2996 ms |
185216 KB |
subtask_3_1.txt |
TLE |
3106 ms |
186880 KB |
subtask_3_2.txt |
TLE |
3139 ms |
186880 KB |
subtask_3_3.txt |
WA |
804 ms |
65792 KB |
subtask_3_4.txt |
WA |
834 ms |
67328 KB |
subtask_3_5.txt |
WA |
1932 ms |
125312 KB |
subtask_3_6.txt |
WA |
2524 ms |
161664 KB |
subtask_3_7.txt |
TLE |
3158 ms |
187136 KB |
subtask_3_8.txt |
TLE |
3119 ms |
186880 KB |