oj.uz

Submission #233808

# Submission time Handle Problem Language Result Execution time Memory
233808 2020-05-21T18:57:41 Z AQT Toll (APIO13_toll) C++14
100 / 100
 2114 ms 20192 KB 
// Problem : APIO '13 P2 - Toll
// Contest : DMOJ
// URL : https://dmoj.ca/problem/apio13p2
// Memory Limit : 32 MB
// Time Limit : 1200 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

using namespace std;

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

int N, M, K;
edge lst[300005], sp[25], good[100005];
bool st[100005], vis[100005], used[25];
int dsu[100005], par[100005], dep[100005], val[100005], who[100005], wt[100005], rt[25];
vector<pair<int, int>> graph[100005];
vector<edge> cedge, splst;
long long cwt[25], dp[25];

int getrt(int n){
	return dsu[n] = (dsu[n] == n ? n : getrt(dsu[n]));
}

void dfs1(int n){
	for(auto e : graph[n]){
		if(e.first != par[n]){
			par[e.first] = n;
			dep[e.first] = dep[n] + 1;
			val[e.first] = e.second;
			dfs1(e.first);
		}
	}
}

void dfs2(int n){
	vis[n] = 1;
	cwt[who[n]] += wt[n];
	for(auto e : graph[n]){
		if(e.first != par[n]){
			par[e.first] = n;
			who[e.first] = who[n];
			dfs2(e.first);
		}
	}
}

void dfs3(int n){
	dp[n] = cwt[n];
	for(auto e : graph[n]){
		if(e.first != par[n]){
			par[e.first] = n;
			dep[e.first] = dep[n] + 1;
			val[e.first] = e.second;
			dfs3(e.first);
			dp[n] += dp[e.first];
		}
	}
}

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	for(int i = 1; i<=M; i++){
		int a, b, c;
		cin >> a >> b >> c;
		lst[i] = {a, b, c};
	}
	for(int i = 0; i<K; i++){
		int a, b;
		cin >> a >> b;
		sp[i] = {a, b, -1};
	}
	for(int i = 1; i<=N; i++){
		cin >> wt[i];
		dsu[i] = i;
	}
	sort(lst+1, lst+1+M);
	int idx = 0;
	for(int i = 1; i<=M; i++){
		if(getrt(lst[i].u) != getrt(lst[i].v)){
			dsu[getrt(lst[i].u)] = getrt(lst[i].v);
			good[++idx] = lst[i];
		}
	}
	for(int k = 0; k<K; k++){
		for(int i = 1; i<=N; i++){
			dsu[i] = i;
			par[i] = 0;
			graph[i].clear();
		}
		for(int i = 1; i<N; i++){
			if(!st[i]){
				//par[getrt(good[i].u)] = getrt(good[i].v);
				//cout << good[i].v << " " << good[i].u << endl;
				graph[good[i].u].emplace_back(good[i].v, good[i].w);
				graph[good[i].v].emplace_back(good[i].u, good[i].w);
			}
		}
		for(auto e : splst){
			graph[e.u].emplace_back(e.v, -1);
			graph[e.v].emplace_back(e.u, -1);
			dsu[getrt(e.u)] = getrt(e.v);
		}
		if(getrt(sp[k].u) == getrt(sp[k].v)){
			continue;
		}
		dep[1] = 1;
		dfs1(1);
		int x = sp[k].u, y = sp[k].v, value = 0;
		while(x != y){
			if(dep[x] < dep[y]){
				swap(x, y);
			}
			value = max(value, val[x]);
			x = par[x];
		}
		for(int i = 1; i<N; i++){
			if(good[i].w == value){
				st[i] = 1;
			}
		}
		splst.push_back(sp[k]);
	}
	for(int i = 1; i<=N; i++){
		graph[i].clear();
		par[i] = 0;
	}
	for(int i = 1; i<N; i++){
		if(!st[i]){
			graph[good[i].u].emplace_back(good[i].v, good[i].w);
			graph[good[i].v].emplace_back(good[i].u, good[i].w);
		}
		else{
			cedge.push_back(good[i]);
		}
	}
	int C = 0;
	for(int i = 1; i<=N; i++){
		if(!vis[i]){
			who[i] = ++C;
			rt[C] = i;
			dfs2(i);
		}
	}
	N = C;
	K = splst.size();
	sort(cedge.begin(), cedge.end());
	assert(who[1] == 1);
	//reverse(cedge.begin(), cedge.end());
	for(auto &e : splst){
		e.v = who[e.v];
		e.u = who[e.u];
		assert(e.v != e.u);
	}
	for(auto &e : cedge){
		e.v = who[e.v];
		e.u = who[e.u];
		assert(e.v != e.u);
	}
	long long ans = 0;
	for(int mask = 1; mask<1<<K; mask++){
		for(int i = 1; i<=N; i++){
			dsu[i] = i;
			graph[i].clear();
			used[i-1] = 0;
		}
		for(int k = 0; k<K; k++){
			if(mask>>k&1){
				dsu[getrt(splst[k].u)] = getrt(splst[k].v);
				graph[splst[k].u].emplace_back(splst[k].v, -1);
				graph[splst[k].v].emplace_back(splst[k].u, -1);				
			}
		}
		for(int i = 0; i<cedge.size(); i++){
			edge e = cedge[i];
			if(getrt(e.u) != getrt(e.v)){
				dsu[getrt(e.u)] = getrt(e.v);
				graph[e.u].emplace_back(e.v, e.w);
				graph[e.v].emplace_back(e.u, e.w);
				used[i] = 1;
				//cout << mask << " " << i << endl;
			}
		}
		dfs3(1);
		for(int i = 0; i<cedge.size(); i++){
			if(!used[i]){
				//cout << i << endl;
				int x = cedge[i].u, y = cedge[i].v;
				while(x != y){
					if(dep[x] < dep[y]){
						swap(x, y);
					}
					if(val[x] == -1){
						val[x] = cedge[i].w;
					}
					x = par[x];
				}
			}
		}
		long long tot = 0;
		for(int k = 0; k<K; k++){
			if(mask>>k&1){
				if(dep[splst[k].u] < dep[splst[k].v]){
					swap(splst[k].u, splst[k].v);
				}
				assert(val[splst[k].u] != -1);
				//cout << dp[splst[k].u] << " " << val[splst[k].u] << "\n";
				tot += dp[splst[k].u] * val[splst[k].u];
			}
		}
		ans = max(ans, tot);
	}
	cout << ans << "\n";
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:184:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<cedge.size(); i++){
                  ~^~~~~~~~~~~~~
toll.cpp:195:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<cedge.size(); i++){
                  ~^~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 11 ms 3016 KB Output is correct
6 Correct 9 ms 2944 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 11 ms 3016 KB Output is correct
6 Correct 9 ms 2944 KB Output is correct
7 Correct 428 ms 19960 KB Output is correct
8 Correct 442 ms 20192 KB Output is correct
9 Correct 454 ms 19960 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 11 ms 3016 KB Output is correct
6 Correct 9 ms 2944 KB Output is correct
7 Correct 428 ms 19960 KB Output is correct
8 Correct 442 ms 20192 KB Output is correct
9 Correct 454 ms 19960 KB Output is correct
10 Correct 1698 ms 20088 KB Output is correct
11 Correct 2114 ms 19960 KB Output is correct
12 Correct 2113 ms 19960 KB Output is correct