oj.uz

답안 #441696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441696 2021-07-05T20:28:41 Z AriaH 통행료 (APIO13_toll) C++11
100 / 100
 1569 ms 18504 KB 
/// how the FUCK my nk log2 solution didnt pass and this FUCKING nk2 stupied solution passed
#pragma GCC optimize("O2")
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 238 ms 12116 KB Output is correct
8 Correct 239 ms 12028 KB Output is correct
9 Correct 239 ms 12104 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 238 ms 12116 KB Output is correct
8 Correct 239 ms 12028 KB Output is correct
9 Correct 239 ms 12104 KB Output is correct
10 Correct 1208 ms 12000 KB Output is correct
11 Correct 1569 ms 18500 KB Output is correct
12 Correct 1546 ms 18504 KB Output is correct