oj.uz

Submission #380401

# Submission time Handle Problem Language Result Execution time Memory
380401 2021-03-21T14:32:55 Z couplefire Toll (APIO13_toll) C++17
100 / 100
 2139 ms 12416 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);
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d%d%d", &N, &M, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:38:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  for (int i=1;i<=M;i++) scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].c);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:39:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  for (int i=1;i<=K;i++) scanf("%d%d", &F[i].a, &F[i].b);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:40:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  for (int i=1;i<=N;i++) scanf("%d", A+i);
      |                         ~~~~~^~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 205 ms 12380 KB Output is correct
8 Correct 211 ms 12268 KB Output is correct
9 Correct 207 ms 12320 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 205 ms 12380 KB Output is correct
8 Correct 211 ms 12268 KB Output is correct
9 Correct 207 ms 12320 KB Output is correct
10 Correct 1772 ms 12308 KB Output is correct
11 Correct 2139 ms 12396 KB Output is correct
12 Correct 2086 ms 12416 KB Output is correct