oj.uz

Submission #15934

# Submission time Handle Problem Language Result Execution time Memory
15934 2015-08-02T06:37:37 Z myungwoo Toll (APIO13_toll) C++14
100 / 100
 2246 ms 7588 KB 
#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];
lld subtree_sz[23], sz[23];
vector <int> con[23], tcon[23], tconv[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 dfs(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];
		if (t == from) continue;
		H[t] = H[n] + 1; up[t] = v; tpar[t] = n; dfs(t, n);
		subtree_sz[n] += subtree_sz[t];
	}
}

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});
		con[a].pb(b); con[b].pb(a);
	}
	for (int i=1;i<=K;i++) F[i].a = num[cp(F[i].a)], F[i].b = num[cp(F[i].b)];
	lld ans = 0;
	for (int msk=1;msk<(1<<K);msk++){
		for (int i=1;i<=C;i++) par[i] = i, tcon[i].clear(), tconv[i].clear();
		bool is_cycle = 0;
		for (int i=1;i<=K;i++) if (msk & (1 << (i-1))){
			int a = cp(F[i].a), b = cp(F[i].b);
			if (a == b){ is_cycle = 1; break; }
			tcon[F[i].a].pb(F[i].b); tconv[F[i].a].pb(2e9);
			tcon[F[i].b].pb(F[i].a); tconv[F[i].b].pb(2e9);
			par[b] = a;
		}
		if (is_cycle) continue;
		vector <EDGE> not_in_mst;
		for (auto &e: critical){
			int a = cp(e.a), b = cp(e.b);
			if (a == b) not_in_mst.pb(e);
			else{
				par[b] = a;
				tcon[e.a].pb(e.b); tconv[e.a].pb(0);
				tcon[e.b].pb(e.a); tconv[e.b].pb(0);
			}
		}
		H[1] = 1; dfs(1, 0);
		for (auto &e: not_in_mst){
			int a = e.a, b = e.b;
			if (H[a] < H[b]) swap(a, b);
			while (H[a] > H[b]){
				up[a] = min(up[a], e.c);
				a = tpar[a];
			}
			while (a != b){
				up[a] = min(up[a], e.c); up[b] = min(up[b], e.c);
				a = tpar[a]; b = tpar[b];
			}
		}
		lld val = 0;
		for (int i=2;i<=C;i++) val += up[i] * subtree_sz[i];
		ans = max(ans, val);
	}
	printf("%lld\n", ans);
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 7588 KB Output is correct
2 Correct 230 ms 7588 KB Output is correct
3 Correct 222 ms 7588 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1872 ms 7588 KB Output is correct
2 Correct 2225 ms 7588 KB Output is correct
3 Correct 2246 ms 7588 KB Output is correct