oj.uz

Submission #73881

# Submission time Handle Problem Language Result Execution time Memory
73881 2018-08-29T08:06:57 Z 김세빈(#2276) Toll (APIO13_toll) C++11
16 / 100
 5 ms 2868 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct edge{
	ll u, v, c;
	edge() {}
	edge(ll u, ll v, ll c) : u(u), v(v), c(c) {}
};

vector <edge> E;
vector <ll> V[101010];
ll P[101010], S[101010], C[101010];
ll n, m, k, u, v, ans;

ll find(ll p) { return p == P[p]? p : P[p] = find(P[p]); }

ll dfs(ll p, ll r)
{
	S[p] = C[p];
	for(ll &t: V[p]){
		if(t != r) S[p] += dfs(t, p);
	}
	return S[p];
}

ll check(ll x)
{
	ll i;
	
	for(i=1; i<=n; i++){
		V[i].clear();
		P[i] = i; S[i] = 0; 
	}
	
	for(edge &e: E){
		if(e.c == x){
			if(find(u) != find(v)){
				P[find(u)] = find(v);
				V[u].push_back(v);
				V[v].push_back(u);
			}
			else return 0;
		}
		if(find(e.u) != find(e.v)){
			P[find(e.u)] = find(e.v);
			V[e.u].push_back(e.v);
			V[e.v].push_back(e.u);
		}
	}
	
	dfs(1, 0);
	
	return min(S[u], S[v]) * x;
}

int main()
{
	ll i, a, b, c;
	
	scanf("%lld%lld%lld", &n, &m, &k);
	
	for(i=1; i<=m; i++){
		scanf("%lld%lld%lld", &a, &b, &c);
		E.emplace_back(a, b, c);
	}
	
	sort(E.begin(), E.end(), [&](edge &ea, edge &eb){
		return ea.c < eb.c;
	});
	
	scanf("%lld%lld", &u, &v);
	
	for(i=1; i<=n; i++){
		scanf("%lld", C + i);
	}
	
	for(i=0; i<m; i++){
		ans = max(ans, check(E[i].c));
	}
	
	printf("%lld\n", ans);
	
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &u, &v);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
toll.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", C + i);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
3 Incorrect 5 ms 2868 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
3 Incorrect 5 ms 2868 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
3 Incorrect 5 ms 2868 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
3 Incorrect 5 ms 2868 KB Output isn't correct
4 Halted 0 ms 0 KB -