Submission #3915672
Source Code Expand
#include<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<list>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll>
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;
struct edge
{
long long from; long long to; long long cost;
bool operator<(const edge& rhs) const {
return cost > rhs.cost;
}
};
priority_queue<edge> pq;
ll const MAX = 4006;
ll dep[MAX];
ll parent_uf[MAX];
ll rk[MAX];
void init(ll n) {
for (ll i = 1; i <= n; i++) {
parent_uf[i] = i;
rk[i] = 1;
}
}
ll find(ll x) {
if (parent_uf[x] == x) {
return x;
}
parent_uf[x] = find(parent_uf[x]);
return parent_uf[x];
}
bool same(ll x, ll y) {
return find(x) == find(y);
}
void unite(ll x, ll y) {
if (!same(x, y)) {
x = parent_uf[x];
y = parent_uf[y];
if (rk[x] < rk[y]) {
parent_uf[x] = y;
}
else {
parent_uf[y] = x;
if (rk[x] == rk[y]) {
rk[x]++;
}
}
}
}
ll n, m, q;
vector<edge> G[MAX];
ll make_tree() {
ll cnt = n - 1;
ll ttl = 0;
while (cnt > 0) {
edge cur = pq.top();
pq.pop();
ll cf = cur.from; ll ct = cur.to; ll cc = cur.cost;
if (!same(cf, ct)) {
unite(cf, ct);
ttl += cur.cost;
G[cf].push_back({ cf,ct,cc });
G[ct].push_back({ ct,cf,cc });
cnt--;
}
}
return ttl;
}
ll parent[MAX];
ll costing[MAX];
void dfs() {
parent[1] = 1;
stack<ll> st;
st.push(1);
dep[1] = 0;
while (!st.empty()) {
ll cur = st.top();
st.pop();
for (ll i = 0; i < SIZE(G[cur]); i++) {
ll next = G[cur][i].to;
if (next == parent[cur]) {
continue;
}
//cout << cur << " " << next << endl;
parent[next] = cur;
dep[next] = dep[cur] + 1;
costing[next] = G[cur][i].cost;
//cout << costing[next] << endl;
st.push(next);
}
}
}
ll dp[MAX][MAX] = {};
ll query(ll s, ll t, ll u) {
if (s == t) {
return u;
}
if (dep[s] < dep[t]) {
swap(s, t);
}
if (dp[s][t] != 0) {
return max(dp[s][t],u);
}
ll v = max(u, costing[s]);
//cout << v << " ?" << endl;
dp[s][t] = query(parent[s], t, v);
return dp[s][t];
}
int main() {
cin >> n >> m;
init(n);
REP(i, 1, m) {
ll a, b, c;
cin >> a >> b >> c;
pq.push({ a,b,c });
}
ll ttl = make_tree();
dfs();
cin >> q;
REP(i, 1, q) {
ll s, t;
cin >> s >> t;
cout << ttl - query(s, t, 0) << endl;
}
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
nejineji |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
2908 Byte |
Status |
WA |
Exec Time |
661 ms |
Memory |
138088 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
200 / 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, 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 |
384 KB |
sample_2.txt |
AC |
1 ms |
384 KB |
subtask_1_1.txt |
AC |
3 ms |
2560 KB |
subtask_1_10.txt |
AC |
203 ms |
75116 KB |
subtask_1_11.txt |
AC |
1 ms |
384 KB |
subtask_1_2.txt |
AC |
51 ms |
40564 KB |
subtask_1_3.txt |
AC |
394 ms |
88040 KB |
subtask_1_4.txt |
AC |
9 ms |
13184 KB |
subtask_1_5.txt |
AC |
25 ms |
84800 KB |
subtask_1_6.txt |
AC |
116 ms |
80880 KB |
subtask_1_7.txt |
AC |
388 ms |
75496 KB |
subtask_1_8.txt |
AC |
11 ms |
23424 KB |
subtask_1_9.txt |
AC |
32 ms |
95228 KB |
subtask_2_1.txt |
WA |
408 ms |
135656 KB |
subtask_2_2.txt |
WA |
405 ms |
133992 KB |
subtask_2_3.txt |
WA |
405 ms |
135016 KB |
subtask_2_4.txt |
WA |
405 ms |
134888 KB |
subtask_2_5.txt |
WA |
40 ms |
124544 KB |
subtask_2_6.txt |
WA |
58 ms |
125176 KB |
subtask_2_7.txt |
WA |
132 ms |
126960 KB |
subtask_2_8.txt |
WA |
427 ms |
134504 KB |
subtask_3_1.txt |
WA |
644 ms |
137704 KB |
subtask_3_2.txt |
WA |
650 ms |
138088 KB |
subtask_3_3.txt |
WA |
271 ms |
127360 KB |
subtask_3_4.txt |
WA |
284 ms |
127356 KB |
subtask_3_5.txt |
WA |
463 ms |
132716 KB |
subtask_3_6.txt |
WA |
550 ms |
134760 KB |
subtask_3_7.txt |
WA |
653 ms |
137448 KB |
subtask_3_8.txt |
WA |
661 ms |
137448 KB |