Submission #39205

#	Time	Username	Problem	Language	Result	Execution time	Memory
39205		qoo2p5	Toll (APIO13_toll)	C++14	16 / 100	9 ms	2876 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 = 5005;
const int L = 13;

struct Edge {
	int u, v, c;
	
	bool operator<(const Edge &e) const {
		return c < e.c;
	}
};

int n, m, k;
ll amount[N];
ll n_amount[N];
Edge e[N], my[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 up[N][L];
int tin[N], tout[N];
int tmr;

void calc_up(int v, int f = -1) {
	if (f == -1) {
		tmr = 0;
		fill(up[v], up[v] + L, v);
		depth[v] = 0;
	} else {
		up[v][0] = f;
		rep(i, 1, L) {
			up[v][i] = up[up[v][i - 1]][i - 1];
		}
	}
	tin[v] = tmr++;
	for (auto &e : g[v]) {
		int u = e.first;
		if (u == f) {
			continue;
		}
		depth[u] = depth[v] + 1;
		calc_up(u, v);
	}
	tout[v] = tmr - 1;
}

int go(int v, int h) {
	rep(i, 0, L) {
		if (h & (1 << i)) {
			v = up[v][i];
		}
	}
	return v;
}

int lca(int u, int v) {
	if (depth[u] < depth[v]) {
		swap(u, v);
	}
	u = go(u, depth[u] - depth[v]);
	if (u == v) return u;
	per(i, L - 1, 0) {
		int uu = up[u][i];
		int vv = up[v][i];
		if (uu != vv) {
			u = uu;
			v = vv;
		}
	}
	return up[u][0];
}

bool check_st(int st, int v) {
	return tin[st] <= tin[v] && tout[v] <= tout[st];
}

bool check_path(int u, int v, int w, int a, int b) {
	if (depth[a] < depth[b]) {
		swap(a, b);
	}
	return !check_st(a, w) && (check_st(a, u) || check_st(a, v));
}

bool taken[N];
ll mi[N];
vector<pair<ll, ll>> opt;

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) {
			opt.pb({t, mi[id]});
		}
		res += t;
	}
	return res;
}

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);
		}
		map<int, int> cool;
		rep(i, 1, n + 1) {
			int v = get(i);
			n_amount[v] += amount[i];
			cool[v] = -1;
		}
		int ptr = 1;
		for (auto &it : cool) {
			amount[ptr] = n_amount[it.first];
			it.second = ptr++;
		}
		n = sz(cool);
		/*map<pair<int, int>, int> edges;
		rep(i, 0, m) {
			int u = cool[get(e[i].u)];
			int v = cool[get(e[i].v)];
			if (u > v) {
				swap(u, v);
			}
			if (u != v) {
				if (!edges.count({u, v})) {
					edges[{u, v}] = e[i].c;
				} else {
					mini(edges[{u, v}], e[i].c);
				}
			}
		}
		m = sz(edges);
		ptr = 0;
		for (auto &it : edges) {
			e[ptr++] = {it.first.first, it.first.second, it.second};
		}
		rep(i, 0, k) {
			my[i].u = cool[get(my[i].u)];
			my[i].v = cool[get(my[i].v)];
			assert(my[i].u != my[i].v);
		}*/
		rep(i, 0, m) {
			e[i].u = cool[get(e[i].u)];
			e[i].v = cool[get(e[i].v)];
		}
		rep(i, 0, k) {
			my[i].u = cool[get(my[i].u)];
			my[i].v = cool[get(my[i].v)];
		}
	}
	
	ll ans = 0;
	
	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;
		}
		
		memset(taken, 0, sizeof taken);
		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_up(1);
		
		rep(i, 0, m) {
			if (!taken[i]) {
				int u = e[i].u;
				int v = e[i].v;
				int w = lca(u, v);

				rep(j, 0, k) {
					if (!(mask & (1 << j))) {
						continue;
					}
					
					int a = my[j].u;
					int b = my[j].v;
					assert(abs(depth[a] - depth[b]) == 1);
					if (check_path(u, v, w, a, b)) {
						mini(mi[j], e[i].c);
					}
				}
			}
		}
		
		opt.clear();
		dfs(1);
		assert(sz(opt) == cnt);
		ll cur = 0;
		for (auto &it : opt) {
			cur += it.first * it.second;
		}
		maxi(ans, cur);
	}
	
	cout << ans << "\n";
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:72:40: 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:42: 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);
                                          ^

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