Submission #1986390


Source Code Expand

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}

using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

// Problem Specific Parameter:

// Description: 素集合を管理するデータ構造
// TimeComplexity: 初期化$\mathcal{O}(n)$ 更新$\mathcal{O}(\log n)$
// Verifyed: AOJ DSL_1_A

struct Union_find {
	Union_find(int n) {par.resize(n), iota(_all(par), 0);}
	int find(int x) {return (par[x] == x) ? x : par[x] = find(par[x]);}
	void unite(int a, int b) {a = find(a), b = find(b); par[a] = b;}
	bool same(int a, int b) {return find(a) == find(b);}
	vector<int> par;
};

using edge = struct {int to; ll cost;};
using G = vector<vector<edge>>;
G graph;

const int limit = 4010;
ll dist[limit][limit];

void dfs(int v, int p, int s, ll c) {
	chmax(dist[s][v], c);
	for (auto &e : graph[v]) {
		if (e.to == p) continue;
		dfs(e.to, v, s, max(c, e.cost));
	}
}

int main(void) {
	int n, m;
	cin >> n >> m;

	using edge = tuple < ll, ll, ll>;
	vector<edge> edges;

	rep(i, m) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		edges.push_back(edge(c, a, b));
	}

	sort(begin(edges), end(edges));
	Union_find uf(n);

	ll res = 0LL;
	graph = G(n);

	for (auto &e : edges) {
		ll c, a, b;
		tie(c, a, b) = e;
		if (uf.same(a, b)) continue;
		uf.unite(a, b);
		res += c;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
	}

	rep(v, n) dfs(v, -1, v, 0LL);

	int q;
	cin >> q;
	rep(loop, q) {
		int s, t;
		cin >> s >> t;
		s--, t--;
		cout << res - dist[s][t] << endl;
	}
	return 0;
}

Submission Info

Submission Time
Task A - Graph
User Hec
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2668 Byte
Status AC
Exec Time 1022 ms
Memory 138216 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:88:28: warning: narrowing conversion of ‘b’ from ‘ll {aka long long int}’ to ‘int’ inside { } [-Wnarrowing]
   graph[a].push_back({b, c});
                            ^
./Main.cpp:89:28: warning: narrowing conversion of ‘a’ from ‘ll {aka long long int}’ to ‘int’ inside { } [-Wnarrowing]
   graph[b].push_back({a, c});
                            ^

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 × 31
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 3 ms 2688 KB
subtask_1_10.txt AC 615 ms 132076 KB
subtask_1_11.txt AC 1 ms 256 KB
subtask_1_2.txt AC 463 ms 126836 KB
subtask_1_3.txt AC 808 ms 136808 KB
subtask_1_4.txt AC 380 ms 125952 KB
subtask_1_5.txt AC 429 ms 126016 KB
subtask_1_6.txt AC 518 ms 128368 KB
subtask_1_7.txt AC 808 ms 136168 KB
subtask_1_8.txt AC 369 ms 125952 KB
subtask_1_9.txt AC 451 ms 126076 KB
subtask_2_1.txt AC 815 ms 135784 KB
subtask_2_2.txt AC 819 ms 135528 KB
subtask_2_3.txt AC 806 ms 136936 KB
subtask_2_4.txt AC 815 ms 137320 KB
subtask_2_5.txt AC 376 ms 125952 KB
subtask_2_6.txt AC 459 ms 126328 KB
subtask_2_7.txt AC 528 ms 128240 KB
subtask_2_8.txt AC 812 ms 136168 KB
subtask_3_1.txt AC 1013 ms 138216 KB
subtask_3_2.txt AC 1022 ms 136680 KB
subtask_3_3.txt AC 603 ms 127360 KB
subtask_3_4.txt AC 664 ms 127356 KB
subtask_3_5.txt AC 828 ms 132716 KB
subtask_3_6.txt AC 929 ms 135784 KB
subtask_3_7.txt AC 1016 ms 136808 KB
subtask_3_8.txt AC 1012 ms 137704 KB