Submission #39120

#	Time	Username	Problem	Language	Result	Execution time	Memory
39120		qoo2p5	Toll (APIO13_toll)	C++14	16 / 100	0 ms	2452 KiB

toll

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
const ld EPS = (ld) 1e-7;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (int i = f; i < t; i++)
#define per(i, f, t) for (int i = f; i >= t; i--)

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (y > x) {
        x = y;
        return true;
    }
    return false;
}

void add(ll &x, ll y) {
	x += y;
	if (x >= MOD) x -= MOD;
	if (x < 0) x += MOD;
}

ll mult(ll x, ll y) {
	return x * y % MOD;
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

const int N = 5005;

struct Edge {
	int u, v, c;
	
	bool operator<(const Edge &e) const {
		return c < e.c;
	}
};

int n, m, k;
int amount[N];
Edge e[N], my[N];
int p[N];
vector<pair<int, bool>> g[N];

int get(int v) {
	return (p[v] == v ? v : (p[v] = get(p[v])));
}

bool unite(int u, int v) {
	u = get(u);
	v = get(v);
	if (u == v) {
		return 0;
	}
	p[u] = v;
	return 1;
}

void clr() {
	rep(i, 0, n + 1) {
		p[i] = i;
		g[i].clear();
	}
}

pair<ll, ll> dfs(int v, int f, ll &mx) {
	pair<ll, ll> res = {0, amount[v]};
	for (auto &e : g[v]) {
		if (e.first == f) {
			continue;
		}
		auto tmp = dfs(e.first, v, mx);
		if (e.second) {
			res.first += tmp.second;
			maxi(mx, tmp.second);
		}
		res.first += tmp.first;
		res.second += tmp.second;
	}
	return res;
}

void run() {
	cin >> n >> m >> k;
	rep(i, 0, m) {
		cin >> e[i].u >> e[i].v >> e[i].c;
	}
	sort(e, e + m);
	rep(i, 0, k) {
		cin >> my[i].u >> my[i].v;
	}
	rep(i, 1, n + 1) {
		cin >> amount[i];
	}
	
	ll init = 0;
	{
		clr();
		rep(i, 0, m) {
			init += e[i].c * unite(e[i].u, e[i].v);
		}
	}
	
	ll ans = 0;
	
	rep(mask, 1, 1 << k) {
		clr();
		bool ok = 1;
		int cnt = 0;
		rep(i, 0, k) {
			if (mask & (1 << i)) {
				ok &= unite(my[i].u, my[i].v);
				g[my[i].u].pb({my[i].v, true});
				g[my[i].v].pb({my[i].u, true});
				cnt++;
			}
		}
		if (!ok) {
			continue;
		}
		
		ll rest = init;
		
		rep(i, 0, m) {
			if (unite(e[i].u, e[i].v)) {
				rest -= e[i].c;
				g[e[i].u].pb({e[i].v, false});
				g[e[i].v].pb({e[i].u, false});
			}
		}
		
		if (cnt > rest) {
			continue;
		}
		
		ll mx = 0;
		dfs(1, -1, mx).first;
		ll cur = mx * (rest);
		maxi(ans, cur);
	}
	
	cout << ans << "\n";
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:72:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".in", "r", stdin);
                                        ^
toll.cpp:73:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".out", "w", stdout);
                                          ^

• Subtask 1: 16 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22