Submission #996322


Source Code Expand

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define F first
#define S second

const int MAXN = 4e5 + 10;

int n, m, from[MAXN], to[MAXN], w[MAXN], sec[MAXN], q;
int par[MAXN], ss[4010][4010];
ll sm;
vector<pair<int, int>>	adj[MAXN];
bool vis[4010];

bool cmp(int u, int v){return w[u] < w[v];}

int getPar(int v){return par[v]==v?v:par[v]=getPar(par[v]);}

void dfs(int v, int p, int z = -1){
	ss[p][v] = z;
	vis[v] = 1;
	for (auto e:adj[v])
		if (!vis[e.F])
			dfs(e.F, p, max(z, e.S));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> from[i] >> to[i] >> w[i], from[i]--, to[i]--;
	iota(sec, sec + m, 0);
	sort(sec, sec + m, cmp);
	iota(par, par + n, 0);
	for (int i = 0; i < m; i++){
		int e = sec[i];
		int u = from[e], v = to[e];
		int pu = getPar(u), pv = getPar(v);
		if (pu == pv)	continue;
		adj[u].push_back({v, w[e]});
		adj[v].push_back({u, w[e]});
		par[pu] = pv;
		sm += w[e];
	}
	for (int i = 0; i < n; i++){
		memset(vis, 0, sizeof(vis));
		dfs(i, i);
	}
	cin >> q;
	while (q--){
		int u, v;	cin >> u >> v, u--, v--;
		printf("%lld\n", sm - ss[u][v]);
	}
	return 0;
}

Submission Info

Submission Time
Task A - Graph
User Deemo
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1232 Byte
Status AC
Exec Time 629 ms
Memory 79872 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 200 / 200 300 / 300 200 / 200
Status
AC × 2
AC × 12
AC × 21
AC × 29
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 11 ms 9728 KB
sample_2.txt AC 11 ms 9728 KB
subtask_1_1.txt AC 12 ms 10112 KB
subtask_1_10.txt AC 504 ms 75648 KB
subtask_1_11.txt AC 11 ms 9600 KB
subtask_1_2.txt AC 451 ms 73088 KB
subtask_1_3.txt AC 597 ms 78720 KB
subtask_1_4.txt AC 398 ms 72576 KB
subtask_1_5.txt AC 430 ms 72576 KB
subtask_1_6.txt AC 463 ms 74112 KB
subtask_1_7.txt AC 595 ms 78720 KB
subtask_1_8.txt AC 392 ms 72576 KB
subtask_1_9.txt AC 435 ms 72704 KB
subtask_2_1.txt AC 597 ms 78720 KB
subtask_2_2.txt AC 594 ms 78720 KB
subtask_2_3.txt AC 592 ms 78720 KB
subtask_2_4.txt AC 598 ms 78720 KB
subtask_2_5.txt AC 387 ms 72576 KB
subtask_2_6.txt AC 442 ms 72832 KB
subtask_2_7.txt AC 473 ms 74112 KB
subtask_2_8.txt AC 587 ms 78720 KB
subtask_3_1.txt AC 626 ms 79872 KB
subtask_3_2.txt AC 629 ms 79872 KB
subtask_3_3.txt AC 432 ms 73856 KB
subtask_3_4.txt AC 473 ms 73856 KB
subtask_3_5.txt AC 538 ms 76800 KB
subtask_3_6.txt AC 581 ms 78336 KB
subtask_3_7.txt AC 627 ms 79872 KB
subtask_3_8.txt AC 625 ms 79872 KB