Submission #1282848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282848		yf_yusuf	Toll (APIO13_toll)	C++20	16 / 100	13 ms	8292 KiB

toll

//```//    YF YUSUF
#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
// #include <set>
// #include <map>
// #include <algorithm>
// #include <cmath>
// #include <numeric>
// #include <queue>
// #include <stack>
// #include <cassert>
// #include <climits>
// #include <string>
// #include <cstdlib>
// #include <random>
// #include <iomanip>
// #include <ctime>
using namespace std;
#ifdef YF_CHECK
	bool LOCAL = 1;
#else
	#pragma GCC optimize ("unroll-loops")
	#pragma GCC optimize ("inline")
	#pragma GCC optimize ("Ofast")
	#pragma GCC optimize ("O3")
	bool LOCAL = 0;
#endif
using ll   = long long;
using ld   = long double;
using vll  = vector <ll>;
using mll  = map <ll,ll>;
using pll  = pair <ll,ll>;
using vvl  = vector <vll>;
using vpll = vector <pll>;
template<class T>T MIN(T&a,T b){a=min(a,b);return a;}
template<class T>T MAX(T&a,T b){a=max(a,b);return a;}
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sgr v+v+1,(tl+tr)/2+1,tr
#define sgl v+v,tl,(tl+tr)/2
#define pb push_back
#define ins insert
#define S second
#define F first
mt19937_64 MT(time(0));
ll BP(ll a,ll b,ll mod=1e9+7){
	if(b==0)return 1;
	ll q=BP(a,b/2,mod);
	return ((q*q)%mod*(b%2?a:1ll))%mod;
}
ll f(ll x){return x*(x+1)/2;}
ll dup(ll a,ll b){return (a+b-1)/b;}
ll lcm(ll a,ll b){return a/__gcd(a,b)*b;}
ll invf(ll x){return (-1+sqrt(1+8*x))/2;}
ll lg(ll x){return (x ? 63 - __builtin_clzll(x) : -1);}
const ll  mod=998244353;
const ll  INF=1e18;
const ll  inf=1e9+7;
const ll  N  =1e6+7;
vll a(N);
vpll KK,g[N];
ll ans,n,m,k;
ll used[N];
map<pll,ll> W;
ll mx;
struct DSU{
	vll p,sz;
	vvl g; 
	vll b, d, pr;
	void build(ll n){
		p.resize(n+1, 0);
		sz.resize(n+1, 1);
		g.resize(n+1,(vll){});
		b.resize(n+1, 0);
		d.resize(n+1, 0);
		pr.resize(n+1,0);
		for(int i=1;i<=n;i++){
			p[i] = i;
			sz[i] = 1;
		}
	}
	ll get(ll x){
		if(p[x]==x)return x;
		else return p[x] = get(p[x]);
	}
	bool check(ll a,ll b){
		a = get(a);
		b = get(b);
		return (a!=b);
	}
	bool up(ll a,ll b){
		ll A = a, B = b;
		a = get(a);
		b = get(b);
		if(a==b)return 0;
		if(sz[a] < sz[b])swap(a,b);
		p[b] = a;
		sz[a] += sz[b];
		sz[b] = 0;
		g[A].pb(B);
		g[B].pb(A);
		return 1;
	}
	void dp(ll v=1,ll p=1){
		for(auto to : g[v]){
			if(to!=p){
				d[to] = d[v] + 1;
				pr[to] = v;
				dp(to, v);
			}
		}
	}
	void dfs(ll v,ll p){
		b[v] = a[v];
		for(auto to : g[v])if(to!=p){
			dfs(to, v);
			b[v] += b[to];
		}
	}
};
struct st_LCA{
	ll timer;
	vll tin, tout;
	vll up[20], mx[20];
	ll start, n;
	vvl g;
	void dfs(ll v){
		tin[v] = ++timer;
		for(auto to : g[v]){
			dfs(to);
		}
		tout[v] = ++timer;
	}
	st_LCA(const vll &p) {
    n = p.size() - 1;
    g.resize(n+1);
    tin.resize(n+1);
    tout.resize(n+1);
    mx[0].resize(n+1);
    up[0] = p;
    for(int i = 1; i <= n; i++) {
    	ll to = p[i];
      if(!up[0][i]) start = i;
      else{
      	mx[0][i] = W[{to, i}];
      	g[up[0][i]].pb(i);
      }
    }
    dfs(start);
    for(int j = 1; j < 20; j++) {
      up[j].resize(n + 1);
      mx[j].resize(n + 1);
      for(int i=1;i<=n;i++){
      	up[j][i] = up[j-1][up[j-1][i]];
      	mx[j][i] = max(mx[j-1][i], mx[j-1][up[j-1][i]]);
      }
    }
  }
  bool check(ll a,ll b){return (tin[a] < tin[b] && tout[b] < tout[a]);}
  ll lca(ll a,ll b){
  	if(check(a, b))return a;
  	if(check(b, a))return b;
  	for(int i=19; 0<=i; i--){
  		ll u = up[i][a];
  		if(!u)continue;
  		if(check(u, b))continue;
  		a = u;
  	}
  	return up[0][a];
  }
  ll get(ll a,ll b){
  	ll mxA = 0;
  	ll mxB = 0;
  	for(int i=19; 0<=i; i--){
  		ll u = up[i][a];
  		if(!u)continue;
  		if(check(u, b))continue;
  		MAX(mxA, mx[i][a]);
  		a = u;
  	}
  	a = up[0][a];
  	for(int i=19; 0<=i; i--){
  		ll u = up[i][b];
  		if(!u)continue;
  		if(check(u, a))continue;
  		MAX(mxB, mx[i][b]);
  		b = u;
  	}
  	return max(mxA, mxB);
  }
};
void YF_MAIN(ll TEST){
	cin>>n>>m>>k;
	set<vll> e;
	ll wk[k]{};
	for(int i=1;i<=m;i++){
		ll v,u,w;
		cin>>v>>u>>w;
		W[{v,u}] = W[{u, v}] = w;
		g[v].pb({w,u});
		g[u].pb({w,v});
		e.ins({w,1,u,v});
	}
	// DSU MST;
	// MST.build(n);
	// for(auto V : e){
		// if(MST.up(V[2], V[3]));
	// }
	// MST.dp();
	// st_LCA LCA(MST.pr);
	for(int i=1;i<=k;i++){
		ll v,u;
		cin>>v>>u;
		KK.pb({v,u});
		// wk[i-1] = LCA.get(v, u);
		// cout<<wk[i-1]<<" ";
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ll ans = 0;
	for(int mask = 0; mask < (1<<k); mask++){
		vpll A, B, C;
		{
			bool can = 1;
			DSU check;check.build(n);
			for(int i=0; i<k; i++)if((mask>>i)&1){
				auto [v, u] = KK[i];
				A.pb(KK[i]);
				if(!check.up(v, u)){
					can = 0;
					break;
				}
			}
			if(!can)continue;
			for(auto V : e){
				if(check.up(V[2], V[3])){
					B.pb({V[2], V[3]});
				}
				else{
					C.pb({V[2], V[3]});
				}
			}
		}
		DSU mst; mst.build(n);
		for(auto [v, u] : B)
			mst.up(v, u);
		// if(mask == (1<<k) - 1){
			// for(int i=1;i<=n;i++){
				// cout<<mst.p[i]<<" ";
			// }
			// cout<<"\n";
		// }
		vll wk(A.size(), 0);
		for(auto [v, u] : C){
			ll V = mst.get(v);
			ll U = mst.get(u);
			if(V != U){
			// if(mask == (1<<k) - 1)cout<<V<<" "<<U<<" VU\n";
				for(int i=0; i < A.size(); i++){
					ll vv = mst.get(A[i].F);
					ll uu = mst.get(A[i].S);
					// if(mask == (1<<k) - 1)cout<<vv<<" "<<uu<<" vvuu: ";
					if((vv == V && uu == U) || (vv == U && uu == V)){
						// if(mask == (1<<k) - 1)cout<<"TRUE\n";
						// if(mask == (1<<k) - 1)cout<<i<<" "<<v<<" "<<u<<" WK\n";
						wk[i] = W[{v, u}];
						mst.up(A[i].F, A[i].S);
						break;
					}
					// if(mask == (1<<k) - 1)cout<<"FALSE\n";
				}
			}
		}
		mst.dfs(1, 1);
		mst.dp(1, 1);
		ll now = 0;
		for(int i=0; i < A.size(); i++){
			auto [v, u] = A[i];
			if(mst.d[v] > mst.d[u])swap(v, u);
			now += wk[i] * mst.b[u];
		}
		MAX(ans, now);
		if(mask == (1<<k) - 1){
			for(int i=0; i < A.size(); i++){
				auto [v, u] = A[i];
				// cout<<v<<" "<<u<<" "<<wk[i]<<"\n";
			}
		}
	}
	cout<<ans;
}
const bool TECT=0;
const bool FLSH=1;
const ll SN=1e0 + 7; ll SM[SN];
const ll FN=1e0 + 7; ll FACT[FN], inv[FN], FMOD=inf;
ll PNK(ll n,ll k){return FACT[n] *inv[n-k]%FMOD;}
ll CNK(ll n,ll k){return PNK(n,k)*inv[k  ]%FMOD;}
void BEFORE(){
	for(ll i=2;i<SN;i++){
		if(SM[i])continue;
		for(ll j=i;j<SN;j+=i)
			MAX(SM[j],i);
	}
	FACT[0]=inv[0]=1;
	for(int i=1;i<FN;i++){
		FACT[i]=FACT[i-1]*i%FMOD;
		inv[i]=BP(FACT[i],FMOD-2,FMOD);
	}
}
signed main(){
	// freopen(("input.txt"),"r",stdin);freopen(("output.txt"),"w",stdout);
	if(FLSH){
		ios_base::sync_with_stdio(0);
		cout.setf(ios::fixed);
		cout.precision(0);
		cout.tie(0);
		cin.tie(0);
	}
	cout<<(0 && LOCAL ? "\nYF_OUTPUT:\n\n" : "");
	int TEST=1;
	if(TECT)
		cin>>TEST;
	BEFORE();
	for(int T=1;T<=TEST;T++){
		// cout<<"Case "<<T<<": ";
		YF_MAIN(T);
		cout<<(T==TEST ? "" : "\n");
	}
	return 0;
} 
//   YF YUSUF ```

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