oj.uz

Submission #490163

# Submission time Handle Problem Language Result Execution time Memory
490163 2021-11-26T02:37:38 Z 8e7 Toll (APIO13_toll) C++17
100 / 100
 1758 ms 14324 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 100005
#define maxc 25
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct edge {
	int u, v, w;
	edge(){u = v = w = 0;}
	edge(int x, int y, int z){u = x, v = y, w = z;}
};
vector<edge> ed;
 
struct DSU{
	int par[maxn];
	void init(int n) {
		for (int i = 0;i <= n;i++) par[i] = i;
	}
	int find(int a) {
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	void Union(int a, int b) { // set par[a] = b
		par[find(a)] = find(b);
	}
} dsu, comp, built;
 
bool mark[maxn];
int vis[maxn];
int wei[maxc], pa[maxc], dep[maxc];
int minres[maxc][maxc]; // minres: minimum restricting edge weight
int c[maxn];
ll p[maxc], siz[maxc];
vector<pii> small[maxc];
void dfs(int n, int par, int d, ll &ans) { //builds small tree sizes
	siz[n] = p[n];
	pa[n] = par;
	dep[n] = d;
	for (auto v:small[n]) {
		if (v.ff != par) {
			dfs(v.ff, n, d+1, ans);
			siz[n] += siz[v.ff];
			if (v.ss) {
				//debug(v.ff, siz[v.ff], wei[v.ff]);
				ans += siz[v.ff] * wei[v.ff];
			}
		}
	}
}
void addedge(int a, int b, int val) { //updates added edges
	if (dep[a] < dep[b]) swap(a, b);
	while (dep[a] > dep[b]) {
		wei[a] = min(wei[a], val);
		a = pa[a];
	}	
	while (a != b) {
		wei[a] = min(wei[a], val), wei[b] = min(wei[b], val);
		a = pa[a], b = pa[b];
	}
}
int main() {
	io
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 0;i < m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		ed.push_back(edge(u, v, w));
	}
	sort(ed.begin(), ed.end(), [&](edge x, edge y){return x.w < y.w;});
	dsu.init(n);
	built.init(n);
	vector<edge> add, tree, rep;
	for (int i = 0;i < k;i++) {
		int u, v;
		cin >> u >> v;
		mark[u] = mark[v] = 1;
		built.Union(u, v);
		add.push_back(edge(u, v, 0));
	}
	for (int i = 1;i <= n;i++) cin >> c[i];
	for (auto e:ed) {
		if (dsu.find(e.u) != dsu.find(e.v)) {
			dsu.Union(e.u, e.v);
			tree.push_back(e);
		}	
	}
	dsu.init(n);
	int ind = 0;
	for (auto e:tree) {
		e.u = dsu.find(e.u), e.v = dsu.find(e.v);
		if (mark[e.u] && mark[e.v]) {
			if (built.find(e.u) == built.find(e.v)) rep.push_back(e); 
			else {
				dsu.Union(e.u, e.v);
			}
		} else if (mark[e.u] || mark[e.v]) {
			if (mark[e.u]) swap(e.u, e.v);
			dsu.Union(e.u, e.v);
		} else {
			dsu.Union(e.u, e.v);
		}
		built.Union(e.u, e.v);
	}
	for (int i = 1;i <= n;i++) {
		int f = dsu.find(i);
		if (!vis[f]) {
			vis[f] = ++ind;
		}
		p[vis[f]-1] += c[i];
		//debug("comp", i, vis[f] -1);
	}	
	for (auto &e:add) {
		e.u = vis[dsu.find(e.u)]-1, e.v = vis[dsu.find(e.v)]-1;
		//debug(e.u, e.v);
	}
	//debug();
	for (auto &e:rep) {
		e.u = vis[dsu.find(e.u)]-1, e.v = vis[dsu.find(e.v)]-1;
	}
	ll ans = 0;
	assert(rep.size() <= k);
	for (int i = 1;i < (1<<k);i++) {
		for (int j = 0;j < ind;j++) small[j].clear(), wei[j] = 1<<30;
		//debug(i);
		comp.init(ind);
		bool cy = 0;
		for (int j = 0;j < k;j++) {
			if (i & (1<<j)) {
				small[add[j].u].push_back({add[j].v, 1});
				small[add[j].v].push_back({add[j].u, 1});	
				//debug(add[j].u, add[j].v, comp.find(add[j].u), comp.find(add[j].v));
				if (comp.find(add[j].u) == comp.find(add[j].v)) {
					cy = 1;
					break;
				}
				comp.Union(add[j].u, add[j].v);
			}
		}
		if (cy) continue;
		vector<edge> lim;
		for (auto e:rep) {
			if (comp.find(e.u) == comp.find(e.v)) {
				lim.push_back(e);
			} else {
				comp.Union(e.u, e.v);
				small[e.u].push_back({e.v, 0});
				small[e.v].push_back({e.u, 0});
			}
		}	
		//pary(lim, lim + rs);
		ll tmp = 0;
		dfs(0, 0, 0, tmp);
		for (auto e:lim) addedge(e.u, e.v, e.w);
		tmp = 0;
		dfs(0, 0, 0, tmp);
		ans = max(ans, tmp);	
		//debug(i, tmp);	
	}	
	cout << ans << endl;
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50

8 8 2
1 2 1
1 3 5
2 7 7
4 7 2
4 6 8
1 6 6
3 8 3
5 8 4
2 4
3 5
1 1 1 1 1 1 1 1 

6 5 4
1 2 2
1 3 3
3 4 1
4 5 5
5 6 4
2 3
3 5
2 5
4 6
3 2 4 1 1 2
*/

Compilation message

In file included from toll.cpp:10:
toll.cpp: In function 'int main()':
toll.cpp:143:20: warning: comparison of integer expressions of different signedness: 'std::vector<edge>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  143 |  assert(rep.size() <= k);
      |         ~~~~~~~~~~~^~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 162 ms 7916 KB Output is correct
8 Correct 163 ms 14236 KB Output is correct
9 Correct 164 ms 14284 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 162 ms 7916 KB Output is correct
8 Correct 163 ms 14236 KB Output is correct
9 Correct 164 ms 14284 KB Output is correct
10 Correct 1471 ms 14324 KB Output is correct
11 Correct 1741 ms 14260 KB Output is correct
12 Correct 1758 ms 14320 KB Output is correct