Submission #138610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138610	2019-07-30T07:18:43 Z	김세빈(#3318)	Farm and factory (CERC12_F)	C++14	1 / 1	1768 ms	63984 KB

F

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;
typedef long double ld;

priority_queue <pll> Q;
vector <pll> G[101010];
ll D1[101010], D2[101010];
ll X[101010], Y[101010];

void dijkstra(ll n, ll p, ll *D)
{
	ll i, d;
	
	for(i=1; i<=n; i++){
		D[i] = 1e18;
	}
	
	D[p] = 0; Q.emplace(0, p);
	
	for(; !Q.empty(); ){
		tie(d, p) = Q.top(); Q.pop();
		if(-d != D[p]) continue;
		for(pll &t: G[p]){
			if(D[t.first] > t.second - d){
				D[t.first] = t.second - d;
				Q.emplace(d - t.second, t.first);
			}
		}
	}
}

ld tc()
{
	ll n, m, i, u, v, c;
	ll c1, c2, s;
	
	scanf("%lld%lld", &n, &m);
	
	for(i=1; i<=n; i++){
		G[i].clear();
	}
	
	for(i=1; i<=m; i++){
		scanf("%lld%lld%lld", &u, &v, &c);
		G[u].emplace_back(v, c);
		G[v].emplace_back(u, c);
	}
	
	dijkstra(n, 1, D1);
	dijkstra(n, 2, D2);
	
	for(i=1; i<=n; i++){
		D1[i] <<= 1; D2[i] <<= 1;
		X[i] = D1[i] + D2[i];
		Y[i] = D1[i] - D2[i];
	}
	
	sort(X + 1, X + n + 1);
	sort(Y + 1, Y + n + 1);
	
	c1 = X[n + 1 >> 1]; c2 = Y[n + 1 >> 1];
	tie(c1, c2) = pll(c1 + c2 >> 1, c1 - c2 >> 1);
	
	s = 0;
	
	for(i=1; i<=n; i++){
		s += max(abs(D1[i] - c1), abs(D2[i] - c2));
	}
	
	return (ld)s / n / 2;
}

int main()
{
	ll t;
	
	scanf("%lld", &t);
	
	for(; t--; ){
		printf("%.20Lf\n", tc());
	}
	
	return 0;
}

Compilation message

F.cpp: In function 'ld tc()':
F.cpp:65:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  c1 = X[n + 1 >> 1]; c2 = Y[n + 1 >> 1];
         ~~^~~
F.cpp:65:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  c1 = X[n + 1 >> 1]; c2 = Y[n + 1 >> 1];
                             ~~^~~
F.cpp:66:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  tie(c1, c2) = pll(c1 + c2 >> 1, c1 - c2 >> 1);
                    ~~~^~~~
F.cpp:66:37: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  tie(c1, c2) = pll(c1 + c2 >> 1, c1 - c2 >> 1);
                                  ~~~^~~~
F.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
F.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
F.cpp: In function 'int main()':
F.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &t);
  ~~~~~^~~~~~~~~~~~

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	38 ms	2924 KB	Output is correct
3	Correct	1768 ms	63984 KB	Output is correct