Submission #860707

#	Time	Username	Problem	Language	Result	Execution time	Memory
860707		beaboss	Toll (APIO13_toll)	C++14	16 / 100	1 ms	2140 KiB

toll

// Source: https://oj.uz/problem/view/APIO13_toll
//

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

struct DSU {
	vector<ll> e;
	DSU(ll N) { e = vector<ll>(N, -1); }

	// get representive component (uses path compression)
	ll get(ll x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

	bool same_set(ll a, ll b) { return get(a) == get(b); }

	ll size(ll x) { return -e[get(x)]; }

	bool unite(ll x, ll y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return true;
	}
};

ll sz[25];

ll total = 0;

vi people(1e5 + 10);
ll dfs(ll cur, vector<vpii> &adj_ne, vector<vi> &adj_ol, ll par = -1) {

	ll subt = 0;
	for (auto val: adj_ne[cur]) {
		if (val.f == par) continue;
		ll thr = dfs(val.f, adj_ne, adj_ol, cur);
		subt += thr;
		total += thr * val.s;
	}

	for (auto val: adj_ol[cur]) {
		if (val == par) continue;
		subt += dfs(val, adj_ne, adj_ol, cur);
	}
	subt += sz[cur];

	return subt; 
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll n, m, k;
	cin >> n >> m >> k;

	vector<pair<ll, pii> > og(m);

	ll a, b, c;
	FOR(i, 0, m) {
		cin >> a >> b >> c;
		og[i]={c, {a, b}};
	}

	sort(og.begin(), og.end());

	vpii e;
	for (auto val: og) e.pb(val.s);

	DSU full(n+1);
	vpii ne;

	FOR(i, 0, k) {
		cin >> a >> b;
		ne.pb({a, b});
		full.unite(a, b);
	}

	FOR(i, 1, n + 1) cin >> people[i];

	vi merge;

	FOR(i, 0, m) {
		if (full.unite(e[i].f, e[i].s)) merge.pb(i);
	}

	DSU split(n + 1);

	for (auto val: merge) split.unite(e[val].f, e[val].s);

	// extract connected components

	vi to_cc(n + 1, -1);
	ll cc = 0;
	FOR(i, 1, n + 1) {
		if (to_cc[split.get(i)] == -1) {
			to_cc[split.get(i)] = cc++;
		}


		// cout << i << ' '
		to_cc[i] = to_cc[split.get(i)];
		sz[to_cc[split.get(i)]] += people[i];
		// cout << to_cc[i] << i << endl;
	}


	// get rep
	vi rep;

	set<pii> used;

	FOR(i, 0, m) {
		if (split.get(e[i].f) > split.get(e[i].s)) swap(e[i].f, e[i].s); 

		if (!split.same_set(e[i].f, e[i].s) && used.find({split.get(e[i].f), split.get(e[i].s)}) == used.end()) {
			used.insert({split.get(e[i].f), split.get(e[i].s)});
			used.insert({split.get(e[i].s), split.get(e[i].f)});
			rep.pb(i);
			// cout << i << endl;
		}
	}

	// find weights for new edges

	vi we(k, -1);

	FOR(i, 0, k) {
		// assert(!split.same_set(ne[i].f, ne[i].s));
		for (auto val: rep) {
			// cout << e[val].f << e[val].s << endl;
			if ((to_cc[e[val].f] == to_cc[ne[i].f] && to_cc[e[val].s] == to_cc[ne[i].s]) || (to_cc[e[val].s] == to_cc[ne[i].f] && to_cc[e[val].f] == to_cc[ne[i].s])) {
				// cout << 'd' << endl;
				// assert(we[i]==-1);
				we[i]=og[val].f;
				
			}
		}

		assert(we[i] != -1);
	}


	ll ans = 0;
	// cout << (1 << k) << endl;
	FOR(i, 0, (1 << k)) {
		DSU test(cc+1);
		bool cyc=false;

		vector<vpii> adj_ne(cc);
		vector<vi> adj_ol(cc);

		// cout << to_cc[ne[0].f] << to_cc[ne[0].s] << endl;

		FOR(j, 0, k) {
			if ((1 << j) & i) {
				if (!test.unite(to_cc[ne[j].f], to_cc[ne[j].s])) {
					cyc=true;
					break;
				}

				adj_ne[to_cc[ne[j].f]].pb({to_cc[ne[j].s], we[j]});
				adj_ne[to_cc[ne[j].s]].pb({to_cc[ne[j].f], we[j]});


			}
		}

		if (cyc) continue;

		
		for (auto val: rep) {
			if (test.unite(to_cc[e[val].f], to_cc[e[val].s])) {
				adj_ol[to_cc[e[val].f]].pb(to_cc[e[val].s]);
				adj_ol[to_cc[e[val].s]].pb(to_cc[e[val].f]);
			}
		}

		total = 0;
		// cout << i << endl;
		// for (auto val: adj_ne) cout << val.f << val.s << endl;
		// for (auto val: adj_ol) cout << val.f << val.s << endl;
		dfs(to_cc[1], adj_ne, adj_ol);

		ans = max(ans, total);
		
	}

	cout << ans << endl;


}

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