Submission #94620

#	Time	Username	Problem	Language	Result	Execution time	Memory
94620		qoo2p5	Toll (APIO13_toll)	C++17	100 / 100	1414 ms	19604 KiB

toll

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
const ld EPS = (ld) 1e-7;
const ll MOD = (ll) 1e9 + 7;
 
#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (int i = f; i < t; i++)
#define per(i, f, t) for (int i = f; i >= t; i--)
 
ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}
 
template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}
 
template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (y > x) {
        x = y;
        return true;
    }
    return false;
}
 
void add(ll &x, ll y) {
	x += y;
	if (x >= MOD) x -= MOD;
	if (x < 0) x += MOD;
}
 
ll mult(ll x, ll y) {
	return x * y % MOD;
}
 
void run();
 
#define TASK ""
 
int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}
 
// == SOLUTION == //
 
const int N = (int) 3e5 + 123;
 
struct Edge {
	int u, v, c;
	
	bool operator<(const Edge &e) const {
		return c < e.c;
	}
};
 
int n, m, k;
ll amount[N], n_amount[N];
Edge e[N], my[N];
int id[N];
int p[N];
vector<pair<int, int>> g[N];
 
int get(int v) {
	return (p[v] == v ? v : (p[v] = get(p[v])));
}
 
bool unite(int u, int v) {
	u = get(u);
	v = get(v);
	if (u == v) {
		return 0;
	}
	p[u] = v;
	return 1;
}
 
void clr() {
	rep(i, 0, n + 1) {
		p[i] = i;
		g[i].clear();
	}
}
 
int depth[N];
int par[N], par_e[N];
int tin[N], tout[N];
 
void calc(int v, int f = -1) {
	if (v == -1) {
		depth[v] = 0;
	}
	par[v] = f;
	for (auto &e : g[v]) {
		int u = e.first;
		if (u == f) {
			continue;
		}
		if (e.second >= 0) {
			par_e[u] = e.second;
		} else {
			par_e[u] = -1;
		}
		depth[u] = depth[v] + 1;
		calc(u, v);
	}
}
 
bool taken[N];
ll mi[N];
 
ll cur;
 
ll dfs(int v, int f = -1) {
	ll res = amount[v];
	for (auto &e : g[v]) {
		int u = e.first;
		if (u == f) {
			continue;
		}
		int id = e.second;
		ll t = dfs(u, v);
		if (id >= 0) {
			cur += t * mi[id];
		}
		res += t;
	}
	return res;
}
 
void upd_up(int v, int w) {
	if (par_e[v] != -1) {
		mini(mi[par_e[v]], w);
	}
}
 
void run() {
	cin >> n >> m >> k;
	rep(i, 0, m) {
		cin >> e[i].u >> e[i].v >> e[i].c;
	}
	sort(e, e + m);
	rep(i, 0, k) {
		cin >> my[i].u >> my[i].v;
	}
	rep(i, 1, n + 1) {
		cin >> amount[i];
	}
	
	{
		clr();
		rep(i, 0, k) {
			unite(my[i].u, my[i].v);
		}
		vector<int> used;
		rep(i, 0, m) {
			if (unite(e[i].u, e[i].v)) {
				used.pb(i);
			}
		}
		
		clr();
		for (int i : used) {
			unite(e[i].u, e[i].v);
		}
		
		int ptr = 1;
		
		rep(i, 1, n + 1) {
			int v = get(i);
			if (!id[v]) {
				id[v] = ptr++;
			}
			id[i] = id[v];
			n_amount[id[v]] += amount[i];
		}
		
		n = ptr;
		
		copy(n_amount, n_amount + ptr, amount);
		rep(i, 0, k) {
			my[i].u = id[my[i].u];
			my[i].v = id[my[i].v];
		}
		
		map<pair<int, int>, int> edges;
		rep(i, 0, m) {
			int u = id[e[i].u];
			int v = id[e[i].v];
			if (u > v) {
				swap(u, v);
			}
			if (u == v) {
				continue;
			}
			
			if (edges.count({u, v})) mini(edges[{u, v}], e[i].c);
			else edges[{u, v}] = e[i].c;
		}
		
		ptr = 0;
		for (auto &it : edges) {
			e[ptr++] = {it.first.first, it.first.second, it.second};
		}
		m = ptr;
	}
	
	sort(e, e + m);
	
	{
		clr();
		vector<Edge> need;
		rep(i, 0, m) {
			if (unite(e[i].u, e[i].v)) {
				need.pb(e[i]);
			}
		}
		m = sz(need);
		rep(i, 0, m) {
			e[i] = need[i];
		}
	}
	
	ll ans = 0;
	assert(m <= k);
	
	rep(mask, 1, 1 << k) {
		clr();
		bool ok = 1;
		int cnt = 0;
		rep(i, 0, k) {
			if (mask & (1 << i)) {
				ok &= unite(my[i].u, my[i].v);
				g[my[i].u].pb({my[i].v, i});
				g[my[i].v].pb({my[i].u, i});
				cnt++;
			}
		}
		if (!ok) {
			continue;
		}
		
		fill(taken, taken + m, 0);
		rep(i, 0, m) {
			if (unite(e[i].u, e[i].v)) {
				g[e[i].u].pb({e[i].v, -1});
				g[e[i].v].pb({e[i].u, -1});
				taken[i] = 1;
			}
		}
		
		fill(mi, mi + k, LINF);
		calc(1);
		
		rep(i, 0, m) {
			if (!taken[i]) {
				int u = e[i].u;
				int v = e[i].v;
				if (depth[u] < depth[v]) swap(u, v);
				while (depth[u] > depth[v]) {
					upd_up(u, e[i].c);
					u = par[u];
				}
				while (u != v) {
					upd_up(u, e[i].c);
					upd_up(v, e[i].c);
					u = par[u];
					v = par[v];
				}
			}
		}
		
		cur = 0;
		dfs(1);
		maxi(ans, cur);
	}
	
	cout << ans << "\n";
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'void calc(int, int)':
toll.cpp:130:10: warning: array subscript is below array bounds [-Warray-bounds]
   depth[v] = 0;
   ~~~~~~~^

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