oj.uz

Submission #122442

# Submission time Handle Problem Language Result Execution time Memory
122442 2019-06-28T08:26:39 Z 김세빈(#2988) Toll (APIO13_toll) C++14
16 / 100
 2 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

vector <pll> T[11];
vector <edge> E;
ll P[11], C[33], X[11];
ll n, m, k, x, ans;

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

ll dfs(ll p, ll r)
{
	ll ret = X[p];
	
	for(pll &t: T[p]){
		if(t.first != r){
			if(t.second) x = dfs(t.first, p);
			else ret += dfs(t.first, p);
		}
	}
	
	return ret;
}

int main()
{
	ll i, j, u, v, c;
	
	scanf("%lld%lld%lld", &n, &m, &k);
	
	if(n > 10) return 0;
	
	for(i=0; i<m; i++){
		scanf("%lld%lld%lld", &u, &v, C + i);
		E.emplace_back(u, v, C[i], 0);
	}
	
	scanf("%lld%lld", &u, &v);
	E.emplace_back(u, v, 0, 1);
	
	for(i=1; i<=n; i++){
		scanf("%lld", X + i);
	}
	
	for(i=0; i<m; i++){
		for(edge &e: E){
			if(e.t == 1) e.c = C[i];
		}
		
		sort(E.begin(), E.end(), [&](edge &ea, edge &eb){
			if(ea.c != eb.c) return ea.c < eb.c;
			else return ea.t > eb.t;
		});
		
		for(j=1; j<=n; j++){
			P[j] = j;
			T[j].clear();
		}
		
		for(edge &e: E){
			if(find(e.u) != find(e.v)){
				P[find(e.u)] = find(e.v);
				T[e.u].emplace_back(e.v, e.t);
				T[e.v].emplace_back(e.u, e.t);
			}
		}
		
		x = 0; dfs(1, 0);
		ans = max(ans, x * C[i]);
	}
	
	printf("%lld\n", ans);
	
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:38:17: warning: unused variable 'c' [-Wunused-variable]
  ll i, j, u, v, c;
                 ^
toll.cpp:40: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:45: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 + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:49: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:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", X + i);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 22.0

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