Submission #384775

#	Time	Username	Problem	Language	Result	Execution time	Memory
384775		aarr	Toll (APIO13_toll)	C++14	0 / 100	4 ms	5100 KiB

toll

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 100 * 1000 + 5, M = 300 * 1000 + 5;


int st[M], ed[M];
pair <int, int> e[M];
int a[N];
vector <pair <int, int> > adj[N];
vector <int> vec[N];
int par[N], sz[N];
vector <int> cl;
bool mark[N];
int sm[N];
long long dp[N];

int get_par(int v) {
	if (par[v] == v) {
		return v;
	}
	return get_par(par[v]);
}

void dfs(int v, int mask) {
	mark[v] = true;
	cl.push_back(v);
	sm[v] = sz[v];
	for (auto p : adj[v]) {
		int t = p.second, u = get_par(p.first);
		if (!mark[u] && ((mask >> t) & 1)) {
			dfs(u, mask);
			sm[v] += sm[u];
			dp[v] += dp[u];
			dp[v] += sm[u];
		}
	}
}

int32_t main() {
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++) {
		cin >> st[i] >> ed[i] >> e[i].first;
		e[i].second = i;
	}
	sort(e + 1, e + m + 1);
	for (int i = 0; i < k; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}
	for (int i = 1; i <= n; i++) {
		cin >> sz[i];
		par[i] = i;
	}
	for (int mask = 0; mask < (1 << k); mask++) {
		int x = __builtin_popcount(mask);
		if (n - x - 1 >= 0) {
			vec[n - x - 1].push_back(mask);
		}
	}
	int cnt = 0;
	long long ans = 0;
//	cout << "75 " << endl;
	for (int i = 1; i <= m; i++) {
		int u = get_par(st[e[i].second]), v = get_par(ed[e[i].second]);
		if (u != v) {
			if (adj[v].size() > adj[u].size()) {
				swap(u, v);
			}
			for (auto x : vec[cnt]) {
			//	cout << "71 " << cnt << " " << x << endl;
				int v = get_par(1);
				dfs(v, x);
			//	for (int j = 1; j <= n; j++) {
			//		cout << "72 " << j << " " << par[j] << " " << sm[j] << " " << dp[j] << endl;
			//	}
				if (cl.size() + cnt == n) {
					ans = max(ans, 1ll * dp[v] * e[i].first);
				}
				for (auto x : cl) {
					mark[x] = false;
					dp[x] = sm[x] = false;
				}
				cl.clear();
			}
			par[v] = u;
			sz[u] += sz[v];
		//	for (int j = 1; j <= n; j++) {
		//		cout << "74 " << j << " " << par[j] << " " << sm[j] << " " << dp[j] << endl;
		//	}
			for (auto x : adj[v]) {
				adj[u].push_back(x);
			}

			cnt++;
		}
	}
	cout << ans;
	
	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int32_t main()':
toll.cpp:82:25: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   82 |     if (cl.size() + cnt == n) {
      |         ~~~~~~~~~~~~~~~~^~~~

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