oj.uz

Submission #439819

# Submission time Handle Problem Language Result Execution time Memory
439819 2021-06-30T21:16:27 Z soroush Toll (APIO13_toll) C++17
100 / 100
 1588 ms 18576 KB 
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("sse,sse2,avx,avx2,fma,popcnt")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int , int> pii;

const int maxn = 1e5 + 10;

#define pb push_back
#define ms(x , y) memset(x , y , sizeof x)

int n, m , k;
int a[maxn*3], b[maxn*3], c[maxn*3] , srt[maxn*3] , p[maxn];
int L[maxn], R[maxn], num[maxn] , cnt;
ll sum[maxn], sub[22];
int par[maxn];
vector < int > adj[maxn], mst , e;
int E[22], Eptr = 0;
int ad[22][22][2], adptr[22];
int per[22];

int getpar(int v){
	return ((par[v]) ? par[v] = getpar(par[v]) : v);
}

bool merge (int u , int v){
	if((u = getpar(u)) == (v = getpar(v)))return 0;
	par[u] = v;return 1;
}

int gatpar(int v){
	return ((per[v]) ? per[v] = gatpar(per[v]) : v);
}

bool marge (int u , int v){
	if((u = gatpar(u)) == (v = gatpar(v)))return 0;
	per[u] = v;return 1;
}

void col(int v){
	num[v] = cnt; sum[cnt] += p[v];
	for(auto u : adj[v])if(!num[u]) col(u);
}

int Par[40] , counts[40] , h[40] , mn[40];

void dfs(int v){
	sub[v] = sum[v];
	for(int i = 0 ; i < adptr[v] ; i ++){
		int u = ad[v][i][0] , x = ad[v][i][1];
		if(u ^ Par[v]){
		Par[u] = v , counts[u] = x , h[u] = h[v] + 1;
		dfs(u);
		sub[v] += sub[u];
	}}
}

ll solve(int msk){
	ll ans = 0;
	ms(per , 0);
	for(int i = 0 ; i < k ; i ++)if(msk & (1 << i)){
		if(!marge(L[i] , R[i]))return 0;
	}
	ms(adptr , 0);
	for(int i = 0 ; i < k ; i ++)if(msk & (1 << i)){
		ad[L[i]][adptr[L[i]]][0] = R[i];
		ad[L[i]][adptr[L[i]] ++ ][1] = 1;
		ad[R[i]][adptr[R[i]]][0] = L[i] ,
		ad[R[i]][adptr[R[i]] ++ ][1] = 1;
	}
	Eptr = 0;
	for(int i : e)
		if(marge(a[i] , b[i])){
			ad[a[i]][adptr[a[i]]][0] = b[i];
			ad[a[i]][adptr[a[i]] ++ ][1] = 0;
			ad[b[i]][adptr[b[i]]][0] = a[i] ,
			ad[b[i]][adptr[b[i]] ++ ][1] = 0;
		}
		else 
			E[Eptr++] = i;
	dfs(1);
	ms(mn , 63);
	for(int i = 0 ; i < Eptr ; i ++){
		int e = E[i];
		int u = a[e] , v = b[e] , w = c[e];
		if(h[u] < h[v])swap(u , v);
		while(h[u] ^ h[v]){
			mn[u] = min(mn[u] , w) ,  u = Par[u];
		}
		while(u ^ v)
			mn[u] = min(mn[u] , w) , u = Par[u],
			mn[v] = min(mn[v] , w) , v = Par[v];
	}
	for(int i = 1 ; i <= cnt ; i ++)
		ans += counts[i] * sub[i] * mn[i];
	return ans;
}

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m >> k;
	mst.reserve(32);
	e.reserve(32);
	for(int i = 1 ; i <= m ; i ++)
		cin >> a[i] >> b[i] >> c[i] , srt[i] = i;
	sort(srt + 1 , srt + m + 1 , [](int i , int j){return c[i] < c[j];});
	for(int i = 0 ; i < k ; i ++)	
		cin >> L[i] >> R[i];
	for(int i = 1 ; i <= n ; i ++)
		cin >> p[i];
	for(int i = 1 ; i <= m ; i ++)
		if(merge(a[srt[i]] , b[srt[i]]))mst.pb(srt[i]);
	fill(par + 1, par + n + 1, 0);
	for(int i = 0 ; i < k ; i ++)
		merge(L[i] , R[i]);
	for(int i : mst)
		if(merge(a[i] , b[i]))
			adj[a[i]].pb(b[i]), adj[b[i]].pb(a[i]);
		else
			e.pb(i);
	for(int i = 1 ; i <= n ; i ++)if(!num[i])
		++cnt , col(i);
	for(int i = 0 ; i < k ; i++)
		L[i] = num[L[i]], R[i] = num[R[i]];
	for(auto x : e)
		a[x] = num[a[x]] , b[x] = num[b[x]];
	ll ans = 0;
	for(int i = 0 ; i < (1 << k) ; i ++)
		ans= max(ans , solve(i));
	cout << ans;
	return(0);
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2740 KB Output is correct
5 Correct 5 ms 2892 KB Output is correct
6 Correct 5 ms 2892 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2740 KB Output is correct
5 Correct 5 ms 2892 KB Output is correct
6 Correct 5 ms 2892 KB Output is correct
7 Correct 263 ms 18576 KB Output is correct
8 Correct 290 ms 18460 KB Output is correct
9 Correct 272 ms 18568 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2740 KB Output is correct
5 Correct 5 ms 2892 KB Output is correct
6 Correct 5 ms 2892 KB Output is correct
7 Correct 263 ms 18576 KB Output is correct
8 Correct 290 ms 18460 KB Output is correct
9 Correct 272 ms 18568 KB Output is correct
10 Correct 1247 ms 18568 KB Output is correct
11 Correct 1588 ms 18544 KB Output is correct
12 Correct 1558 ms 18456 KB Output is correct