oj.uz

Submission #667250

# Submission time Handle Problem Language Result Execution time Memory
667250 2022-11-30T22:23:23 Z kirakaminski968 Toll (APIO13_toll) C++11
100 / 100
 1714 ms 14480 KB 
#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;
#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;
    int v; 
    int 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) { 
		par[find(a)] = find(b);
	}
} dsu, comp, built;
bool mark[maxn];
int vis[maxn];
int wei[maxc], pa[maxc], dep[maxc]; 
int c[maxn]; 
ll p[maxc], siz[maxc]; 
vector<pii> small[maxc]; 
void dfs(int n, int par, int d, ll &ans) { 
	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) ans += siz[v.ff] * wei[v.ff];
		}
	}
}
void addedge(int a, int b, int val) { 
	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];
	}	
	for (auto &e:add) e.u = vis[dsu.find(e.u)]-1, e.v = vis[dsu.find(e.v)]-1;
	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;
		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});	
				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});
			}
		}	
		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);
	}	
	cout << ans << endl;
}

Compilation message

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

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 159 ms 14212 KB Output is correct
8 Correct 174 ms 14364 KB Output is correct
9 Correct 161 ms 14328 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 159 ms 14212 KB Output is correct
8 Correct 174 ms 14364 KB Output is correct
9 Correct 161 ms 14328 KB Output is correct
10 Correct 1389 ms 14480 KB Output is correct
11 Correct 1714 ms 14360 KB Output is correct
12 Correct 1696 ms 14340 KB Output is correct