Submission #95974

#	Time	Username	Problem	Language	Result	Execution time	Memory
95974		tmwilliamlin168	Toll (APIO13_toll)	C++14	78 / 100	2538 ms	15948 KiB

toll

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

#define ll long long

const int mxN=1e5, mxK=20, mxM=3e5;
int n, k, m;
array<int, 3> e[mxM];
array<int, 2> a[mxK];
vector<array<int, 2>> adj[mxN];
vector<int> b, r;
ll s[mxN], ans;

struct dsu {
	int p[mxN], r[mxN];
	int find(int x) {
		return x==p[x]?x:(p[x]=find(p[x]));
	}
	bool join(int x, int y) {
		if((x=find(x))==(y=find(y)))
			return 0;
		if(r[x]<r[y])
			swap(x, y);
		p[y]=x;
		r[x]+=r[x]==r[y];
		return 1;
	}
} d1, d2, d3;

bool dfs1(int u, int t, int w, int p=-1) {
	if(u==t)
		return 1;
	for(array<int, 2> &v : adj[u]) {
		if(v[0]==p||!dfs1(v[0], t, w, u))
			continue;
		v[1]=min(w, v[1]);
		return 1;
	}
	return 0;
}

ll dfs2(int u, int p=-1, ll d=0) {
	ll r=d*s[u];
	for(array<int, 2> v : adj[u])
		if(v[0]!=p)
			r+=dfs2(v[0], u, d+v[1]);
	return r;
}

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

	cin >> n >> m >> k;
	for(int i=0; i<m; ++i)
		cin >> e[i][1] >> e[i][2] >> e[i][0], --e[i][1], --e[i][2];
	sort(e, e+m);
	iota(d1.p, d1.p+n, 0);
	for(int i=0; i<k; ++i) {
		cin >> a[i][0] >> a[i][1], --a[i][0], --a[i][1];
		d1.join(a[i][0], a[i][1]);
	}
	for(int i=0; i<n; ++i)
		cin >> s[i];
	iota(d2.p, d2.p+n, 0);
	iota(d3.p, d3.p+n, 0);
	for(int i=0; i<m; ++i) {
		if(!d2.join(e[i][1], e[i][2]))
			continue;
		if(d1.join(e[i][1], e[i][2]))
			d3.join(e[i][1], e[i][2]);
		else
			b.push_back(i);
	}
	for(int i=0; i<n; ++i) {
		if(d3.find(i)==i)
			r.push_back(i);
		else
			s[d3.find(i)]+=s[i];
	}
	for(int bi : b) {
		e[bi][1]=d3.find(e[bi][1]);
		e[bi][2]=d3.find(e[bi][2]);
		adj[e[bi][1]].push_back({e[bi][2], e[bi][0]});
		adj[e[bi][2]].push_back({e[bi][1], e[bi][0]});
	}
	for(int i=0; i<k; ++i) {
		a[i][0]=d3.find(a[i][0]);
		a[i][1]=d3.find(a[i][1]);
	}
	for(int i=0; i<1<<k; ++i) {
		for(int ri : r) {
			adj[ri].clear();
			d1.p[ri]=ri;
			d1.r[ri]=0;
		}
		for(int j=0; j<k; ++j) {
			if(i>>j&1&&d1.join(a[j][0], a[j][1])) {
				adj[a[j][0]].push_back({a[j][1], INT_MAX});
				adj[a[j][1]].push_back({a[j][0], INT_MAX});
			}
		}
		for(int bi : b) {
			if(d1.join(e[bi][1], e[bi][2])) {
				adj[e[bi][1]].push_back({e[bi][2], 0});
				adj[e[bi][2]].push_back({e[bi][1], 0});
			} else {
				dfs1(e[bi][1], e[bi][2], e[bi][0]);
				dfs1(e[bi][2], e[bi][1], e[bi][0]);
			}
		}
		ans=max(dfs2(d3.find(0)), ans);
	}
	cout << ans;
}

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