Submission #552581

#	Time	Username	Problem	Language	Result	Execution time	Memory
552581		QwertyPi	Toll (APIO13_toll)	C++14	100 / 100	1286 ms	115772 KiB

toll

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define int long long
using namespace std;
typedef uint32_t uint;
typedef pair<int, int> pii;
const int N = 1e5+1, K = 21;
vector<int> G[N];
vector<pii> H[K];
int A[N], w[K], sz[K];
unsigned ubits[1 << K], wei[1 << K][K];

struct edge{
	int u, v, w;
	bool operator< (const edge& o) const{
		return w < o.w;
	}
};

struct DSU{
	int dsu[N], w[N];
	void ini(int n, int* A = nullptr){
		for(int i = 0; i <= n; i++) dsu[i] = i;
		if(A != nullptr) for(int i = 0; i <= n; i++) w[i] = A[i];
	}
	int f(int x){
		if(x == dsu[x]) return x;
		return dsu[x] = f(dsu[x]);
	}
	bool join(int x, int y){
		x = f(x), y = f(y);
		if(x == y) return false;
		dsu[x] = y;
		w[y] += w[x];
		return true;
	}
	bool join(edge e){
		return join(e.u, e.v);
	}
} dsu_r, dsu_t;

vector<edge> E, Q, tQ, tmp;

int dfs(int v, int weight = 0, int p = -1){
	sz[v] = dsu_r.w[v];
	int ret = 0;
	for(auto i : H[v]){
		if(i.fi != p){
			ret += dfs(i.fi, i.se, v);
			sz[v] += sz[i.fi];
		}
	}
	ret += sz[v] * weight;
	return ret;
}

int32_t main(){
	int n, m, k, r;
	cin >> n >> m >> k;
	for(int i = 0; i < m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		E.pb({u, v, w});
	}
	for(int i = 0; i < k; i++){
		int u, v; cin >> u >> v;
		Q.pb({u, v});
	}
	for(int i = 1; i <= n; i++){
		cin >> A[i];
	}
	
	sort(E.begin(), E.end());
	dsu_t.ini(n);
	dsu_r.ini(n, A);
	for(int i = 0; i < m; i++){
		if(dsu_t.join(E[i].u, E[i].v)){
			tmp.pb(E[i]);
		}
	}
	swap(E, tmp); tmp.clear();
	
	dsu_t.ini(n);
	for(int i = 0; i < k; i++){
		dsu_t.join(Q[i].u, Q[i].v);
	}
	assert(E.size() == n - 1);
	for(int i = 0; i < n - 1; i++){
		if(dsu_t.join(E[i].u, E[i].v)){
			dsu_r.join(E[i].u, E[i].v);
		}else{
			tmp.pb(E[i]);
		}
	}
	swap(E, tmp); tmp.clear();
	
	for(auto& i : E) i.u = dsu_r.f(i.u), i.v = dsu_r.f(i.v);
	for(auto& i : Q) i.u = dsu_r.f(i.u), i.v = dsu_r.f(i.v);
	int rt;
	{
		set<int> S; map<int, int> M;
		for(auto i : E) S.insert(i.u), S.insert(i.v);
		for(auto i : Q) S.insert(i.u), S.insert(i.v);
		int idx = 0; for(auto i : S) w[idx] = dsu_r.w[i], M[i] = idx++; r = idx;
		for(auto& i : E) i.u = M[i.u], i.v = M[i.v];
		for(auto& i : Q) i.u = M[i.u], i.v = M[i.v];
		rt = M[dsu_r.f(1)];
	}
	int ans = 0;
	
	for(uint mask = 0; mask < (1 << k); mask++){
		dsu_t.ini(r, w), dsu_r.ini(r, w);
		bool fail = false;
		for(int i = 0; i < k; i++){
			if(mask & (1 << i)){
				if(!dsu_t.join(Q[i])) ubits[mask] = -1, fail = true;
			}
		}
		if(fail) continue;
		int ubit = 0;
		for(int i = 0; i < E.size(); i++){
			if(dsu_t.join(E[i])){
				dsu_r.join(E[i]);
			}else{
				ubit |= (1 << i);
			}
		}
		ubits[mask] = ubit;
		for(int i = 0; i < k; i++){
			if((1 << i) & mask){
				uint df = ubits[mask] ^ ubits[mask ^ (1 << i)]; assert((ubits[mask] | ubits[mask ^ (1 << i)]) == ubits[mask]);
				int idx = __builtin_ffs(df) - 1; assert(idx != -1);
				wei[mask][i] = E[idx].w;
			}
		}
		tQ = Q;
		for(int i = 0; i < r; i++) H[i].clear();
		for(int i = 0; i < k; i++){
			if(mask & (1 << i)){
				tQ[i].u = dsu_r.f(tQ[i].u), tQ[i].v = dsu_r.f(tQ[i].v), tQ[i].w = wei[mask][i];
				H[tQ[i].u].pb({tQ[i].v, tQ[i].w});
				H[tQ[i].v].pb({tQ[i].u, tQ[i].w});
			}
		}
		ans = max(ans, dfs(dsu_r.f(rt)));
	}
//	for(int i = 0; i < (1 << k); i++){
//		cout << ubits[i] << ' ';
//	}
//	cout << endl;
//	for(int i = 0; i < (1 << k); i++){
//		for(int j = 0; j < k; j++){
//			cout << wei[i][j] << ' ';
//		}
//		cout << endl;
//	}
//	cout << r << endl;
//	for(int i = 0; i < r; i++){
//		cout << w[i] << ' ';
//	}
//	cout << endl;
//	cout << "E" << endl;
//	for(auto i : E){
//		cout << i.u << ' ' << i.v << ' ' << i.w << endl;
//	}
//	cout << "Q" << endl;
//	for(auto i : Q){
//		cout << i.u << ' ' << i.v << ' ' << i.w << endl;
//	}
	cout << ans << endl;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from toll.cpp:1:
toll.cpp: In function 'int32_t main()':
toll.cpp:89:18: warning: comparison of integer expressions of different signedness: 'std::vector<edge>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   89 |  assert(E.size() == n - 1);
      |         ~~~~~~~~~^~~~~~~~
toll.cpp:113:26: warning: comparison of integer expressions of different signedness: 'uint' {aka 'unsigned int'} and 'int' [-Wsign-compare]
  113 |  for(uint mask = 0; mask < (1 << k); mask++){
      |                     ~~~~~^~~~~~~~~~
toll.cpp:123:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for(int i = 0; i < E.size(); i++){
      |                  ~~^~~~~~~~~~

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