oj.uz

Submission #23511

# Submission time Handle Problem Language Result Execution time Memory
23511 2017-05-11T18:11:58 Z gs14004 Toll (APIO13_toll) C++11
100 / 100
 1856 ms 13844 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
 
struct disj{
	int pa[100005];
	void init(int n){
		for(int i=1; i<=n; i++){
			pa[i] = i;
		}
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;
 
struct edg{
	int s, e, x;
	bool operator<(const edg &e)const{
		return x < e.x;
	}
}a[300005];
 
int n, m, k, s[22], e[22], c[100005];
vector<int> gph[100005];
 
vector<edg> resi;
int p, comp[100005];
lint csize[25];
 
int par[25], pae[25], chk[25], dep[25];
lint sz[25];
vector<pi> gph2[25];
 
void dfs2(int x, int p){
	sz[x] = csize[x];
	for(auto &i : gph2[x]){
		if(i.first == p) continue;
		chk[i.first] = i.second;
		dep[i.first] = dep[x] + 1;
		pae[i.first] = 1e9;
		par[i.first] = x;
		dfs2(i.first, x);
		sz[x] += sz[i.first];
	}
}
 
lint solve(int b){
	for(int i=1; i<=p; i++){
		gph2[i].clear();
	}
	disj.init(p);
	for(int i=0; i<k; i++){
		if((b >> i) & 1){
			if(!disj.uni(s[i], e[i])){
				return -1;
			}
			gph2[s[i]].push_back({e[i], 1});
			gph2[e[i]].push_back({s[i], 1});
		}
	}
	vector<edg> resi2;
	for(auto &i : resi){
		if(disj.uni(i.s, i.e)){
			gph2[i.s].push_back({i.e, 0});
			gph2[i.e].push_back({i.s, 0});
		}
		else{
			resi2.push_back(i);
		}
	}
	dfs2(1, -1);
	for(auto &i : resi2){
		if(dep[i.s] < dep[i.e]) swap(i.s, i.e);
		while(dep[i.s] > dep[i.e]){
			pae[i.s] = min(pae[i.s], i.x);
			i.s = par[i.s];
		}
		while(i.s != i.e){
			pae[i.s] = min(pae[i.s], i.x);
			pae[i.e] = min(pae[i.e], i.x);
			i.s = par[i.s];
			i.e = par[i.e];
		}
	}
	lint ret = 0;
	for(int i=2; i<=p; i++){
		if(chk[i]) ret += sz[i] * pae[i];
	}
	return ret;
}
 
void dfs(int x, int p){
	if(comp[x]) return;
	csize[p] += c[x];
	comp[x] = p;
	for(auto &i : gph[x]){
		dfs(i, p);
	}
}
 
void compress(){
	disj.init(n);
	for(int i=0; i<k; i++){
		disj.uni(s[i], e[i]);
	}
	for(int i=0; i<n-1; i++){
		if(disj.uni(a[i].s, a[i].e)){
			gph[a[i].e].push_back(a[i].s);
			gph[a[i].s].push_back(a[i].e);
		}
		else{
			resi.push_back(a[i]);
		}
	}
	for(int i=1; i<=n; i++){
		if(!comp[i]){
			dfs(i, ++p);
		}
	}
	for(auto &i : resi){
		i.s = comp[i.s];
		i.e = comp[i.e];
	}
	for(int i=0; i<k; i++){
		s[i] = comp[s[i]];
		e[i] = comp[e[i]];
	}
}
 
int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0; i<m; i++){
		scanf("%d %d %d",&a[i].s, &a[i].e, &a[i].x);
	}
	for(int i=0; i<k; i++){
		scanf("%d %d",&s[i],&e[i]);
	}
	for(int i=1; i<=n; i++){
		scanf("%d",&c[i]);
	}
	sort(a, a+m);
	disj.init(n);
	vector<edg> tree;
	for(int i=0; i<m; i++){
		if(disj.uni(a[i].s, a[i].e)){
			tree.push_back(a[i]);
		}
	}
	for(int i=0; i<n-1; i++){
		a[i] = tree[i];
	}
	compress();
	lint ret = 0;
	for(int i=1; i<(1<<k); i++){
		ret = max(ret, solve(i));
	}
	cout << ret;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:139:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
                            ^
toll.cpp:141:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a[i].s, &a[i].e, &a[i].x);
                                              ^
toll.cpp:144:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s[i],&e[i]);
                             ^
toll.cpp:147:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c[i]);
                    ^

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9060 KB Output is correct
2 Correct 0 ms 9060 KB Output is correct
3 Correct 3 ms 9060 KB Output is correct
4 Correct 0 ms 9060 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9060 KB Output is correct
2 Correct 0 ms 9060 KB Output is correct
3 Correct 3 ms 9060 KB Output is correct
4 Correct 0 ms 9060 KB Output is correct
5 Correct 3 ms 9060 KB Output is correct
6 Correct 6 ms 9060 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9060 KB Output is correct
2 Correct 0 ms 9060 KB Output is correct
3 Correct 3 ms 9060 KB Output is correct
4 Correct 0 ms 9060 KB Output is correct
5 Correct 3 ms 9060 KB Output is correct
6 Correct 6 ms 9060 KB Output is correct
7 Correct 293 ms 13844 KB Output is correct
8 Correct 309 ms 13844 KB Output is correct
9 Correct 249 ms 13844 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9060 KB Output is correct
2 Correct 0 ms 9060 KB Output is correct
3 Correct 3 ms 9060 KB Output is correct
4 Correct 0 ms 9060 KB Output is correct
5 Correct 3 ms 9060 KB Output is correct
6 Correct 6 ms 9060 KB Output is correct
7 Correct 293 ms 13844 KB Output is correct
8 Correct 309 ms 13844 KB Output is correct
9 Correct 249 ms 13844 KB Output is correct
10 Correct 1526 ms 13844 KB Output is correct
11 Correct 1856 ms 13844 KB Output is correct
12 Correct 1799 ms 13844 KB Output is correct