oj.uz

Submission #73845

# Submission time Handle Problem Language Result Execution time Memory
73845 2018-08-29T06:36:24 Z 윤교준(#2277) Toll (APIO13_toll) C++11
16 / 100
 3 ms 404 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#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 univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

vector<int> G[35];
vector<int> EV;

int A[55], B[55], C[55], O[55];
int D[35], ud[35];
bitset<35> chk;

ll Ans;
int N, M, K, CA, CB;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

bool dfs(vector<int> &V, int i) {
	chk[i] = true;
	if(i == CB) return true;
	for(int e : G[i]) {
		int v = A[e] + B[e] - i;
		if(chk[v]) continue;
		if(!dfs(V, v)) continue;
		V.eb(e);
		return true;
	}
	return false;
}

ll f(int ne, int i) {
	ll ret = D[i];
	chk[i] = true;
	for(int e : G[i]) {
		if(e == ne) continue;
		int v = A[e] + B[e] - i;
		if(chk[v]) continue;

		ll t = f(ne, v);
		if(t < 0) return t;
		if(!e) return -t;
		ret += t;
	}
	return ret;
}

int main() {
	cin >> N >> M >> K;
	for(int i = 1; i <= M; i++)
		cin >> A[i] >> B[i] >> C[i];
	cin >> CA >> CB;
	for(int i = 1; i <= N; i++) cin >> D[i];
	iota(O, O+M+1, 0);
	sort(O+1, O+M+1, [&](int a, int b) { return C[a] < C[b]; });
	iota(ud, ud+N+1, 0);
	for(int oi = 1, i, a, b; oi <= M; oi++) {
		i = O[oi]; a = A[i]; b = B[i];
		if(uf(a) == uf(b)) continue;
		G[a].eb(i); G[b].eb(i);
		uf(a, b);
	}
	dfs(EV, CA);

	{
		int mxc = 0;
		for(int e : EV) upmax(mxc, C[e]);
		vector<int> V;
		for(int e : EV) if(mxc == C[e]) V.eb(e);
		swap(EV, V);
	}

	A[0] = CA; B[0] = CB;
	G[CA].eb(0); G[CB].eb(0);
	for(int e : EV) {
		chk.reset();
		ll t = -f(e, 1);
		upmax(Ans, t * C[e]);
	}

	cout << Ans << endl;
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 22.0

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