Submission #95987

#	Time	Username	Problem	Language	Result	Execution time	Memory
95987		tmwilliamlin168	Toll (APIO13_toll)	C++14	0 / 100	4 ms	2808 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, r[mxN], p[mxK+1], d[mxK+1], rs, w[mxK+1];
array<int, 3> e[mxM];
array<int, 2> a[mxK];
vector<int> adj[mxN], b;
ll s[mxK+1], ans;

struct n1 {
	int r;
	n1 operator+(const n1 &o) const {
		return r^o.r?n1{max(r, o.r)}:n1{r+1};
	}
	bool operator<(const n1 &o) const {
		return r<o.r;
	}
};

struct n2 {
	int r, a;
	n2 operator+(const n2 &o) const {
		return r^o.r?n2{max(r, o.r), a}:n2{r+1 ,a};
	}
	bool operator<(const n2 &o) const {
		return r<o.r;
	}
};

template<size_t S, class T>
struct dsu {
	int p[S];
	T a[S];
	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;
		a[x]=a[x]+a[y];
		if(a[x]<a[y])
			swap(x, y);
		p[y]=x;
		return 1;
	}
};
dsu<mxN, n1> d1, d2, d3;
dsu<mxK+1, n1> d4;
dsu<mxK+1, n2> d5;

void dfs1(int u, int pu=-1) {
	p[u]=pu;
	d[u]=pu^-1?d[pu]+1:0;
	for(int v : adj[u])
		if(v!=pu)
			dfs1(v, u);
}

ll dfs2(int u, ll d=0) {
	ll r=d*s[u];
	for(int v : adj[u])
		if(v!=p[u])
			r+=dfs2(v, d+w[v]);
	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]);
	}
	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[i]=rs++;
	for(int i=0, si; i<n; ++i) {
		cin >> si;
		s[r[d3.find(i)]]+=si;
	}
	for(int bi : b) {
		e[bi][1]=r[e[bi][1]];
		e[bi][2]=r[e[bi][2]];
	}
	for(int i=0; i<k; ++i) {
		a[i][0]=r[a[i][0]];
		a[i][1]=r[a[i][1]];
	}
	for(int i=0; i<1<<k; ++i) {
		for(int j=0; j<rs; ++j) {
			adj[j].clear();
			d5.a[j]={0, j};
		}
		iota(d4.p, d4.p+rs, 0);
		memset(d4.a, 0, sizeof(d4.a));
		iota(d5.p, d5.p+rs, 0);
		for(int j=0; j<k; ++j) {
			if(i>>j&1&&d4.join(a[j][0], a[j][1])) {
				adj[a[j][0]].push_back(a[j][1]);
				adj[a[j][1]].push_back(a[j][0]);
			}
		}
		deque<array<int, 3>> c;
		for(int bi : b) {
			if(d4.join(e[bi][1], e[bi][2])) {
				adj[e[bi][1]].push_back(e[bi][2]);
				adj[e[bi][2]].push_back(e[bi][1]);
				c.push_front({0, e[bi][1], e[bi][2]});
			} else
				c.push_back(e[bi]);
		}
		dfs1(r[d3.find(0)]);
		for(array<int, 3> ci : c) {
			int u=d5.a[d5.find(ci[1])].a, v=d5.a[d5.find(ci[2])].a;
			while(u^v) {
				if(d[u]<d[v])
					swap(u, v);
				w[u]=ci[0];
				assert(d5.join(p[u], u));
				u=d5.a[d5.find(u)].a;
			}
		}
		ans=max(dfs2(r[d3.find(0)]), ans);
	}
	cout << ans;
}

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