oj.uz

Submission #562958

# Submission time Handle Problem Language Result Execution time Memory
562958 2022-05-15T18:19:02 Z ngpin04 Toll (APIO13_toll) C++14
100 / 100
 2421 ms 15132 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int M = 3e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> adj[N];
vector <int> ind;

long long val[N];

int fr[M];
int to[M];
int w[M];

int T[N][5];
int par[N];
int anc[N];
int lim[N];
int tin[N];
int mx[N];
int lg[N];
int h[N];
int a[N];
int b[N];
int n,k,m,timer;

int getpar(int u) {
	return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}

bool join(int u, int v) {
	u = getpar(u);
	v = getpar(v);
	if (u == v)
		return false;
	if (par[u] > par[v])
		swap(u, v);
	par[u] += par[v];
	par[v] = u;
	return true;
}

int gethigh(int u, int v) {
	return (h[u] < h[v]) ? u : v;
}

void dfs(int u, int p = -1) {
	// cerr << val[u] << " " << u << " " << p << "\n";
	anc[u] = p;
	// tin[u] = ++timer;
	// T[timer][0] = u;
	for (int i : adj[u]) {
		int v = (i < 0) ? (fr[-i] ^ to[-i] ^ u) : (a[i] ^ b[i] ^ u);
		if (v == p)
			continue;
		int c = (i < 0) ? 0 : mx[i];
		lim[v] = c;
		// T[++timer][0] = u;
		h[v] = h[u] + 1;
		dfs(v, u);
	}
}

int getlca(int u, int v) {
	int l = tin[u];
	int r = tin[v];
	if (l > r)
		swap(l, r);
	int d = lg[r - l + 1];
	return gethigh(T[l][d], T[r - bit(d) + 1][d]);
}

long long getans(int u, long long cur = 0, int p = -1) {
	long long res = cur * val[u];
	for (int i : adj[u]) {
		int v = (i < 0) ? (fr[-i] ^ to[-i] ^ u) : (a[i] ^ b[i] ^ u);
		if (v == p)
			continue;
		res += getans(v, cur + lim[v], u);
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++) {
		cin >> fr[i] >> to[i] >> w[i];
		ind.push_back(i);
	}
	for (int i = 1; i <= k; i++)
		cin >> a[i] >> b[i];

	for (int i = 0; i < N; i++)
		lg[i] = __lg(i);

	sort(ALL(ind), [](int i, int j) {
		return w[i] < w[j];
	});
	
	{
		memset(par, -1, sizeof(par));
		vector <int> newind;
		for (int i : ind) {
			if (join(fr[i], to[i])) {
				newind.push_back(i);
				for (int j = 1; j <= k; j++)
					if (!mx[j] && getpar(a[j]) == getpar(b[j]))
						mx[j] = w[i];
			}
		}
		swap(newind, ind);
	}

	vector <int> notind;
	{
		vector <int> newind;
		memset(par, -1, sizeof(par));
		for (int i = 1; i <= k; i++)
			join(a[i], b[i]);

		for (int i : ind) {
			if (join(fr[i], to[i])) 
				newind.push_back(i);
			else
				notind.push_back(i);
		}
		swap(newind, ind);
	}

	memset(par, -1, sizeof(par));
	for (int i : ind) 
		join(fr[i], to[i]);

	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		val[getpar(i)] += x;
	}

	vector <int> node;
	for (int i = 1; i <= n; i++) 
		if (par[i] < 0)
			node.push_back(i);

	for (int i : notind) {
		fr[i] = getpar(fr[i]);
		to[i] = getpar(to[i]);
	}

	for (int i = 1; i <= k; i++) {
		a[i] = getpar(a[i]);
		b[i] = getpar(b[i]);
	}

	long long ans = 0;
	int root = getpar(1);
	for (int mask = 0; mask < bit(k); mask++) {
		for (int v : node) {
			par[v] = -1;
			adj[v].clear();
		}

		bool ok = true;
		for (int i = 1; i <= k; i++) if (getbit(mask, i - 1)) {
			if (!join(a[i], b[i])) {
				ok = false;
				break;
			}
			adj[a[i]].push_back(i);
			adj[b[i]].push_back(i);
		}

		if (!ok)
			continue;

		vector <int> lef;
		for (int i : notind) {
			if (join(fr[i], to[i])) {
				adj[fr[i]].push_back(-i);
				adj[to[i]].push_back(-i);
			} else {
				lef.push_back(i);
			}
		}
		
		timer = 0;
		h[root] = 0;
		dfs(root);

		// for (int j = 1; j < 5; j++)
		// for (int i = 1; i + bit(j) - 1 <= timer; i++)
		// 	T[i][j] = gethigh(T[i][j - 1], T[i + bit(j - 1)][j - 1]);

		for (int v : node)
			par[v] = -1;

		for (int i : lef) {
			// int p = getlca(fr[i], to[i]);
			int u = fr[i];
			int v = to[i];
			while (u != v) {
				if (h[u] > h[v])
					swap(u, v);
				mini(lim[v], w[i]);
				v = anc[v];
			}

			// int v; 
			// {
			// 	v = getpar(fr[i]);
			// 	while (h[v] > h[p]) {
			// 		mini(lim[v], w[i]);
			// 		par[v] = anc[v];
			// 		v = getpar(v);
			// 	}
			// }

			// {
			// 	v = getpar(to[i]);
			// 	while (h[v] > h[p]) {
			// 		mini(lim[v], w[i]);
			// 		par[v] = anc[v];
			// 		v = getpar(v);
			// 	}
			// }
		}

		maxi(ans, getans(root));
	}

	cout << ans;
	return 0;	
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 4 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 5 ms 3540 KB Output is correct
6 Correct 4 ms 3540 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 4 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 5 ms 3540 KB Output is correct
6 Correct 4 ms 3540 KB Output is correct
7 Correct 180 ms 9080 KB Output is correct
8 Correct 209 ms 9020 KB Output is correct
9 Correct 186 ms 9028 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 4 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 5 ms 3540 KB Output is correct
6 Correct 4 ms 3540 KB Output is correct
7 Correct 180 ms 9080 KB Output is correct
8 Correct 209 ms 9020 KB Output is correct
9 Correct 186 ms 9028 KB Output is correct
10 Correct 1769 ms 9004 KB Output is correct
11 Correct 2411 ms 9028 KB Output is correct
12 Correct 2421 ms 15132 KB Output is correct