oj.uz

Submission #95974

# Submission time Handle Problem Language Result Execution time Memory
95974 2019-02-04T20:44:20 Z tmwilliamlin168 Toll (APIO13_toll) C++14
78 / 100
 2500 ms 15948 KB 
#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.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 6 ms 2936 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 159 ms 15892 KB Output is correct
8 Correct 191 ms 15888 KB Output is correct
9 Correct 179 ms 15864 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 6 ms 2936 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 159 ms 15892 KB Output is correct
8 Correct 191 ms 15888 KB Output is correct
9 Correct 179 ms 15864 KB Output is correct
10 Correct 1125 ms 15864 KB Output is correct
11 Correct 2334 ms 15928 KB Output is correct
12 Execution timed out 2538 ms 15948 KB Time limit exceeded