oj.uz

Submission #552581

# Submission time Handle Problem Language Result Execution time Memory
552581 2022-04-23T11:07:39 Z QwertyPi Toll (APIO13_toll) C++14
100 / 100
 1286 ms 115772 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2704 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2704 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 6 ms 3092 KB Output is correct
6 Correct 7 ms 3092 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2704 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 6 ms 3092 KB Output is correct
6 Correct 7 ms 3092 KB Output is correct
7 Correct 372 ms 28316 KB Output is correct
8 Correct 363 ms 28432 KB Output is correct
9 Correct 350 ms 28280 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2704 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 6 ms 3092 KB Output is correct
6 Correct 7 ms 3092 KB Output is correct
7 Correct 372 ms 28316 KB Output is correct
8 Correct 363 ms 28432 KB Output is correct
9 Correct 350 ms 28280 KB Output is correct
10 Correct 1230 ms 115756 KB Output is correct
11 Correct 1286 ms 115772 KB Output is correct
12 Correct 1277 ms 115672 KB Output is correct