oj.uz

Submission #122438

# Submission time Handle Problem Language Result Execution time Memory
122438 2019-06-28T08:20:09 Z 김세빈(#2988) Toll (APIO13_toll) C++14
0 / 100
 2 ms 256 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

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

vector <pii> T[11];
vector <edge> E;
int P[11], C[11], X[11];
int n, m, k, x, ans;

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

int dfs(int p, int r)
{
	int ret = X[p];
	
	for(pii &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()
{
	int i, j, u, v, c;
	
	scanf("%d%d%d", &n, &m, &k);
	
	if(n > 10) return 0;
	
	for(i=0; i<m; i++){
		scanf("%d%d%d", &u, &v, &c);
		E.emplace_back(u, v, c, 0);
		C[i] = c;
	}
	
	scanf("%d%d", &u, &v);
	E.emplace_back(u, v, 0, 1);
	
	for(i=1; i<=n; i++){
		scanf("%d", 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("%d\n", ans);
	
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &u, &v);
  ~~~~~^~~~~~~~~~~~~~~~
toll.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", X + i);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 16.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 22.0

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