Submission #15937

#	Time	Username	Problem	Language	Result	Execution time	Memory
15937		myungwoo	Toll (APIO13_toll)	C++14	78 / 100	2500 ms	7592 KiB

toll

#include <bits/stdc++.h>
using namespace std;

#define MAXN 100005
#define MAXM 300005
#define pb push_back
#define sz(v) ((int)(v).size())
typedef long long lld;

int N, M, K, C;
int A[MAXN];
int par[MAXN], num[MAXN], H[23], tpar[23];
int up[23], is_g[23];
lld subtree_sz[23], sz[23], ans;
vector <int> tcon[23], tconv[23], tcont[23];

struct EDGE{
	int a, b, c;
	bool in_mst, is_critical;
} E[MAXM], F[21];

int cp(int n){ return par[n] == n ? n : (par[n] = cp(par[n])); }

void make_tree(int n, int from)
{
	subtree_sz[n] = sz[n];
	for (int i=sz(tcon[n]);i--;){
		int t = tcon[n][i], v = tconv[n][i], p = tcont[n][i];
		if (t == from) continue;
		H[t] = H[n] + 1; up[t] = v; tpar[t] = n; is_g[t] = p;
		make_tree(t, n);
		subtree_sz[n] += subtree_sz[t];
	}
}

inline void set_edges()
{
	for (int i=1;i<=C;i++) tcon[i].clear(), tconv[i].clear(), tcont[i].clear();
	for (int i=2;i<=C;i++){
		int a = tpar[i], b = i, c = up[i], t = is_g[i];
		if (!a) continue;
		tcon[a].pb(b); tconv[a].pb(c); tcont[a].pb(t);
		tcon[b].pb(a); tconv[b].pb(c); tcont[b].pb(t);
	}
}

void dfs(int n, int cnt)
{
	if (n > K){
		if (!cnt) return;
		lld val = 0;
		for (int i=2;i<=C;i++) if (is_g[i]){
			val += up[i] * subtree_sz[i];
		}
		ans = max(ans, val);
		return;
	}
	dfs(n+1, cnt);
	int a = F[n].a, b = F[n].b;
	if (H[a] < H[b]) swap(a, b);
	vector <int> arr;
	while (H[a] > H[b]) arr.pb(a), a = tpar[a];
	while (a != b) arr.pb(a), arr.pb(b), a = tpar[a], b = tpar[b];
	int mx = 0, target;
	for (int t: arr) if (!is_g[t]){
		if (mx < up[t])
			mx = up[t], target = t;
	}
	if (!mx) return;
	vector <int> _tpar(tpar, tpar+C+1), _is_g(is_g, is_g+C+1), _up(up, up+C+1);
	for (int t: arr) if (is_g[t]) up[t] = min(up[t], mx);
	tpar[target] = 0;
	set_edges();
	a = F[n].a, b = F[n].b;
	tcon[a].pb(b); tconv[a].pb(mx); tcont[a].pb(1);
	tcon[b].pb(a); tconv[b].pb(mx); tcont[b].pb(1);
	make_tree(1, 0);
	dfs(n+1, cnt+1);
	for (int i=1;i<=C;i++)
		tpar[i] = _tpar[i], is_g[i] = _is_g[i], up[i] = _up[i];
	set_edges();
	make_tree(1, 0);
}

int main()
{
	scanf("%d%d%d", &N, &M, &K);
	for (int i=1;i<=M;i++) scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].c);
	for (int i=1;i<=K;i++) scanf("%d%d", &F[i].a, &F[i].b);
	for (int i=1;i<=N;i++) scanf("%d", A+i);
	sort(E+1, E+M+1, [](const EDGE &a, const EDGE &b){
		return a.c < b.c;
	});
	for (int i=1;i<=N;i++) par[i] = i;
	for (int i=1;i<=M;i++){
		int a = cp(E[i].a), b = cp(E[i].b);
		if (a == b) continue;
		par[b] = a;
		E[i].in_mst = 1;
	}
	for (int i=1;i<=N;i++) par[i] = i;
	for (int i=1;i<=K;i++){
		int a = cp(F[i].a), b = cp(F[i].b);
		par[b] = a;
	}
	for (int i=1;i<=M;i++) if (E[i].in_mst){
		int a = cp(E[i].a), b = cp(E[i].b);
		if (a == b) E[i].is_critical = 1;
		par[b] = a;
	}
	for (int i=1;i<=N;i++) par[i] = i;
	for (int i=1;i<=M;i++) if (E[i].in_mst && !E[i].is_critical){
		int a = cp(E[i].a), b = cp(E[i].b);
		if (a > b) swap(a, b);
		par[b] = a;
	}
	for (int i=1;i<=N;i++) if (cp(i) == i){
		num[i] = ++C;
	}
	for (int i=1;i<=N;i++) sz[num[cp(i)]] += A[i];
	vector <EDGE> critical;
	for (int i=1;i<=M;i++) if (E[i].is_critical){
		int a = num[cp(E[i].a)] , b = num[cp(E[i].b)];
		critical.pb({a, b, E[i].c});
	}
	for (int i=1;i<=K;i++) F[i].a = num[cp(F[i].a)], F[i].b = num[cp(F[i].b)];
	for (auto &e: critical){
		tcon[e.a].pb(e.b); tconv[e.a].pb(e.c); tcont[e.a].pb(0);
		tcon[e.b].pb(e.a); tconv[e.b].pb(e.c); tcont[e.b].pb(0);
	}
	make_tree(1, 0);
	dfs(1, 0);
	printf("%lld\n", ans);
}

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