Submission #138646

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138646	2019-07-30T08:00:45 Z	윤교준(#3320)	Farm and factory (CERC12_F)	C++14	1 / 1	1733 ms	25012 KB

F

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define rb(x) ((x)&(-(x)))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAXN = 100055;
const int MAXM = 300055;

ll dp[2][MAXN];

vector<int> G[MAXN];
int A[MAXM], B[MAXM], C[MAXM];

int T, N, M;

void runDijk(ll dp[], int sidx) {
	fill(dp, dp+N+1, INFLL);
	dp[sidx] = 0;
	priority_queue<pli, vector<pli>, greater<pli>> PQ;
	PQ.emplace(0, sidx);
	for(ll dst; !PQ.empty();) {
		int idx; tie(dst, idx) = PQ.top(); PQ.pop();
		if(dp[idx] < dst) continue;
		for(int e : G[idx]) {
			int v = A[e]^B[e]^idx;
			ll ndst = dst + C[e];
			if(dp[v] <= ndst) continue;
			dp[v] = ndst;
			PQ.emplace(ndst, v);
		}
	}
}

void run() {
	cin >> N >> M;
	for(int i = 1; i <= M; i++) {
		cin >> A[i] >> B[i] >> C[i];
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}
	runDijk(dp[0], 1); runDijk(dp[1], 2);

	vector<ll> AV, BV;
	for(int i = 1; i <= N; i++) {
		AV.eb(dp[0][i] + dp[1][i]);
		BV.eb(dp[0][i] - dp[1][i]);
	}
	sorv(AV); sorv(BV);
	ll a = AV[N>>1], b = BV[N>>1], sum = dp[0][2];
	ld x = ld(a+b) / 2, y = ld(a-b) / 2;
	if(x+y < sum) y = sum-x;

	ld ret = 0;
	for(int i = 1; i <= N; i++)
		ret += max(abs(dp[0][i] - x), abs(dp[1][i] - y));
	
	for(int i = 1; i <= N; i++) G[i].clear();
	printf("%.20Lf\n", ld(ret) / N);
	return;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(cin >> T; T--;) run();
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	46 ms	2936 KB	Output is correct
3	Correct	1733 ms	25012 KB	Output is correct