Submission #438800

#	Time	Username	Problem	Language	Result	Execution time	Memory
438800		soroush	Toll (APIO13_toll)	C++17	0 / 100	5 ms	7372 KiB

toll

#include <bits/stdc++.h>

using namespace std;

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n, m, k;
vector < int > adj[maxn] , mst;
vector < pii > e;
int a[maxn] , b[maxn] , c[maxn] , p[maxn] , srt[maxn] , par[maxn];

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


ll marg(int x){
	int v = getpar(a[x]) , u = getpar(b[x]);
	if(u == v)return 0;
	par[v] = u;
	return c[x];
}



ll fish[maxn] , dish;


ll merge(int x){
	int v = getpar(a[x]) , u = getpar(b[x]);
	if(u == v)return 0;
	fish[u] += fish[v];
	par[v] = u;
	return c[x];
}
const int lg = 20;

struct LCA{
	int n;
	int par[lg+3][maxn] , h[maxn];
	vector < pii > adj[maxn];
	ll H[maxn] , sum[maxn];
	void dfs(int v  , int pr){
		sum[v] += p[v];
		for(auto [u, w] : adj[v]) if(u ^ pr)
			H[u] = H[v] + w , h[u] = h[v] + 1 , par[0][u] = v , dfs(u , v) , sum[v] += sum[u];
	}
	void init(int N , int root = 1){
		n = N;
		dfs(root , 0);
		h[0] = -1;
		for(int j = 1 ; j <= lg ; j ++)
			for(int i = 1 ; i <= n ; i ++)
				par[j][i] = par[j - 1][par[j - 1][i]];
	}
	int lca(int u , int v){
		if(h[u] < h[v])
			swap(u , v);
		for(int i = lg ; i >= 0 ; i --)
			if(h[par[i][u]] >= h[v])
				u = par[i][u];
		if(u == v)
			return(u);
		for(int i = lg ; i >= 0 ; i --)
			if(par[i][u] ^ par[i][v])
				u = par[i][u] , v = par[i][v];
		return(par[0][v]);
	}
	int uwdist(int u , int v){
		return h[u] + h[v] - 2 * h[lca(u , v)];
	}
	int dist(int u , int v){
		return(H[u] + H[v] - 2*H[lca(u , v)]);
	}
}lc, cur;

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 0 ; i < m ; i ++){
		cin >> a[i] >> b[i] >> c[i];
		adj[a[i]].pb(i), adj[b[i]].pb(i);
		srt[i] = i;
	}
	for(int i = 0 , u , v ; i < k ; i ++)
		cin >> u >> v, e.pb({u , v});
	for(int i = 1 ; i <= n ; i ++)
		cin >> p[i] , dish += p[i];
	/*
	sort(srt , srt + n , [](int i , int j){return c[i] < c[j];});
	for(int i = 1 ; i <= n ; i ++)
		sort(adj[i].begin(), adj[i].end() , [](int i, int j){return c[i] < c[j];});
	for(int i = 0 ; i < m ; i ++)
		marg(srt[i]);
	ll sum = 0;
	for(int x : mst){
		//lc.adj[a[x]].pb({b[x] , c[x]});
		//lc.adj[b[x]].pb({a[x] , c[x]});
		sum += c[x];
	}
	*/
	//lc.init(n);
	ll ans = 0;
	/*
	for(int i = 0 ; i < (1 << k) ; i ++){
		bool ok = 1;
		for(int j = 0 ; j < k ; j ++)if(i & (1 << j)){
			int u = e[j].first, v = e[j].second;
			if(getpar(u) == getpar(v)){
				ok = 0;
				for(auto [a, b] : e)par[a] = par[b] = 0;
				break;
			}
			par[getpar(v)] = getpar(u);
		}
		if(!ok)continue;
		for(int j = 0 ; j < k ; j ++)if(i & (1 << j)){
			int u = e[j].first, v = e[j].second;
			cur.adj[u].pb({v, 0}) , cur.adj[v].pb({u , 0});
		}
		mst.clear();
		for(int i = 0 ; i < m ; i ++)
			merge(srt[i]);
		for(int x : mst){
			cur.adj[a[x]].pb({b[x] , c[x]});
			cur.adj[b[x]].pb({a[x] , c[x]});
			sum -= c[x];
		}
		cur.init(n);
		for(int i = 1 ; i <= n ; i ++)par[i] = 0;
		for(int j = 0 ; j < k ; j ++)if(i & (1 << j)){
			int u = e[j].first, v = e[j].second;
			int lca = cur.lca(u, v);
			ans += sum * (cur.sum[u ^ v ^ lca]);
		}
	}
	*/
	assert(k == 1);
	auto [u, v] = e[0];
	/*
	for(int i = 0 ; i < (1 << m) ; i ++)if(__builtin_popcount(i) == n - 2){
		for(int j = 1 ; j <= n ; j ++)par[j] = 0 , fish[j] = p[j];
		ll cur = 0;
		for(int j = 0 ; j < m ; j ++)if((1 << j) & i){
			cur += c[j];
			if(getpar(a[j]) == getpar(b[j])){
				cur += 1e14;
				break;
			}
			fish[getpar(b[j])] += fish[getpar(a[j])];
			par[getpar(a[j])] = getpar(b[j]);
		}
		if(getpar(u)  == getpar(v))continue;
		bitset < 10 > bs = i;
		if((sum - cur) * (dish - fish[getpar(1)]) == 420)dokme(sum);
		ans = max(ans , (sum - cur) * (dish - fish[getpar(1)]));
	}
	*/
	/*
	for(int i = 0 ; i < (1 << n) ; i ++){
		int x = i << 1;
		for(int j = 1 ; j <= n ; j ++)par[j] = 0 , fish[j] = p[j];
		ll cur = 0 , mn = 1e9;
		int cnt = 0;
		
		for(int j = 0 ; j < m ; j ++){
			if(x & (1 << a[j]) and x & (1 << b[j])){
				if(getpar(a[j])^getpar(b[j]))cur += c[j], cnt++;
				mn = min(mn , merge(j));
				//cnt ++;
				//if(i == 7)dokme(j);
			}
			else if((x & (1 << a[j])) == 0 and (x & (1 << b[j])) == 0){
				if(getpar(a[j])^getpar(b[j]))cur += c[j] , cnt++;
				mn = min(mn , merge(j));
				//cnt ++;
				//if(i == 7)dokme(j);
			}
			else{
				//if(i == 11)dokme((x & (1 << a[j])));
				mn = min(mn , 1ll * c[j]);
			}
		}//if(i == 11)dokme((getpar(u) == getpar(v)));
		if(cnt != n - 2)continue;
		if(getpar(u) == getpar(v))continue;
		//if( i == 11)dokme("wtF");
		//if(i == 11)dokme(sum);
		if(cur + mn <= sum){
			//if(i == 1)dokme('d');
			ans = max(ans , mn * (dish -  fish[getpar(1)]));
			if(ans == 420)dokme(x);
		}
	}
	*/
	int l = 0 , r = 1e9;
	a[m] = u , b[m] = v;
	srt[m] = m;
	for(int i = 0 ; i < m ; i ++){
		c[m] = c[i];
		sort(srt , srt + m , [](int i , int j){return c[i] < c[j];});
		ll sum = 0;
		for(int i = 1 ; i <= n ; i ++)par[i] = 0 , fish[i] = p[i];
		for(int i = 0 ; i <= m ; i ++)sum += merge(i);
		for(int i = 1 ; i <= n ; i ++)par[i] = 0 , fish[i] = p[i];
		sum -= merge(m);
		int x = 0;
		for(int i = 0 ; i < m ; i ++){
			ll pq = sum;
			sum -= merge(i);
			if(pq ^ sum)x|= (1 << i);
		}
		if(sum == 0){
			//dokme(2);
			for(int i = 1 ; i <= n ; i ++)par[i] = 0 , fish[i] = p[i];
			for(int i = 0 ; i < m ; i ++)if((1 << i) & x)merge(i);
			ans = max(ans , c[i] * 1ll * (dish - fish[getpar(1)]));
		}
	} 
	cout << ans;
	return(0);
}

Compilation message (stderr)

toll.cpp: In function 'int32_t main()':
toll.cpp:208:6: warning: unused variable 'l' [-Wunused-variable]
  208 |  int l = 0 , r = 1e9;
      |      ^
toll.cpp:208:14: warning: unused variable 'r' [-Wunused-variable]
  208 |  int l = 0 , r = 1e9;
      |              ^

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