Submission #1002176
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;
typedef vector<char> vc;
typedef vector<vector<char> > vvc;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
template<class T> using vv=vector<vector< T > >;
typedef deque<int> di;
typedef deque<deque<int> > ddi;
typedef deque<bool> db;
typedef deque<deque<bool> > ddb;
// 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;
UF(int n) : par(n), sizes(n, 1) {
for (int i = 0; i < n; ++i) {
par[i] = i;
}
}
int find(int x) {
if (x == par[x]) return x;
return par[x] = find(par[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
if (sizes[x] < sizes[y]) {
swap(x, y);
}
par[y] = x;
sizes[x] += sizes[y];
sizes[y] = 0;
}
bool same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
return sizes[find(x)];
}
};
int main() {
int n, m;
cin >> n >> m;
vvi edge(m, vi(3));
rep (i, m) {
cin >> 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));
set<int> si;
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];
si.insert(edge[0][1]);
si.insert(edge[0][2]);
FOR (i, 1, m) {
if (!(uf.same(edge[i][1], edge[i][2]))) {
cost += edge[i][0];
uf.unite(edge[i][1], edge[i][2]);
int append;
if (si.find(edge[i][1]) == end(si)) {
append = edge[i][1];
} else {
append = edge[i][2];
}
for (int x : si) {
maxcost[append][x] = maxcost[x][append] = edge[i][0];
}
si.insert(append);
}
}
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 |
0 |
Code Size |
4216 Byte |
Status |
WA |
Exec Time |
1970 ms |
Memory |
86912 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 |
5 ms |
384 KB |
subtask_1_10.txt |
AC |
1203 ms |
73984 KB |
subtask_1_11.txt |
AC |
3 ms |
256 KB |
subtask_1_2.txt |
WA |
768 ms |
65280 KB |
subtask_1_3.txt |
WA |
1772 ms |
84992 KB |
subtask_1_4.txt |
WA |
741 ms |
63360 KB |
subtask_1_5.txt |
WA |
706 ms |
63360 KB |
subtask_1_6.txt |
WA |
916 ms |
68608 KB |
subtask_1_7.txt |
WA |
1795 ms |
84992 KB |
subtask_1_8.txt |
WA |
760 ms |
63360 KB |
subtask_1_9.txt |
WA |
684 ms |
63616 KB |
subtask_2_1.txt |
WA |
1827 ms |
84992 KB |
subtask_2_2.txt |
WA |
1791 ms |
84992 KB |
subtask_2_3.txt |
WA |
1809 ms |
84992 KB |
subtask_2_4.txt |
WA |
1805 ms |
84992 KB |
subtask_2_5.txt |
WA |
759 ms |
63360 KB |
subtask_2_6.txt |
WA |
739 ms |
64256 KB |
subtask_2_7.txt |
WA |
934 ms |
68608 KB |
subtask_2_8.txt |
WA |
1799 ms |
84992 KB |
subtask_3_1.txt |
WA |
1940 ms |
86912 KB |
subtask_3_2.txt |
WA |
1970 ms |
86912 KB |
subtask_3_3.txt |
WA |
898 ms |
65536 KB |
subtask_3_4.txt |
WA |
822 ms |
65664 KB |
subtask_3_5.txt |
WA |
1333 ms |
76032 KB |
subtask_3_6.txt |
WA |
1636 ms |
81408 KB |
subtask_3_7.txt |
WA |
1955 ms |
86912 KB |
subtask_3_8.txt |
WA |
1926 ms |
86912 KB |