oj.uz

Submission #95969

# Submission time Handle Problem Language Result Execution time Memory
95969 2019-02-04T19:48:30 Z tmwilliamlin168 Toll (APIO13_toll) C++14
16 / 100
 4 ms 2936 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

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

int dfs1(int u, int t, int p=-1) {
	if(u==t)
		return INT_MIN;
	int r=INT_MAX;
	for(array<int, 2> v : adj[u])
		if(v[0]!=p)
			r=min(max(dfs1(v[0], t, u), v[1]), r);
	return r;
}

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][1] >> a[i][2], --a[i][1], --a[i][2];
		d1.join(a[i][1], a[i][2]);
	}
	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][1]=d3.find(a[i][1]);
		a[i][2]=d3.find(a[i][2]);
		a[i][0]=dfs1(a[i][1], a[i][2]);
	}
	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][1], a[j][2])) {
				adj[a[j][1]].push_back({a[j][2], a[j][0]});
				adj[a[j][2]].push_back({a[j][1], a[j][0]});
			}
		}
		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});
			}
		}
		ans=max(dfs2(d3.find(0)), ans);
	}
	cout << ans;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2936 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2936 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Incorrect 4 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2936 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Incorrect 4 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2936 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Incorrect 4 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2936 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Incorrect 4 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -