oj.uz

Submission #258732

# Submission time Handle Problem Language Result Execution time Memory
258732 2020-08-06T12:58:05 Z pure_mem Toll (APIO13_toll) C++14
100 / 100
 1995 ms 15904 KB 
#include <bits/stdc++.h>
 
#define ll long long
#define X first
#define Y second
#define MP make_pair
 
using namespace std;
 
const int N = 3e5 + 123;
 
int n, m, k, p[N], pr[N];
pair< int , pair<int, int> > road[N], gr[N];
vector< pair<int, int> > g[N];
vector< int > need;
int comp[N], mins[N];
ll sz[N], lims[N];

void build(int lens){
	for(int i = 1;i <= lens;i++)
		pr[i] = i;
}

int get_pr(int x){
	if(x == pr[x])
		return x;
	return (pr[x] = get_pr(pr[x]));
}

bool merge(int x, int y){
	x = get_pr(x), y = get_pr(y);
	if(x == y)
		return 0;
	pr[x] = y;
	return 1;
}

void dfs(int v){
	comp[v] = comp[0];
	sz[comp[0]] += p[v];
	for(pair<int, int> to: g[v]){
		if(!comp[to.X])
			dfs(to.X);
	}
}

void prep(){
	build(n);
	sort(road + 1, road + m + 1);
	for(int i = 1, j = 0;i <= m;i++){
		if(merge(road[i].Y.X, road[i].Y.Y))
			road[++j] = road[i];	
	}
	build(n);
	//cerr << "w1\n";
	for(int i = 1;i <= k;i++)
		merge(gr[i].Y.X, gr[i].Y.Y);
	for(int i = 1;i < n;i++){
		if(merge(road[i].Y.X, road[i].Y.Y)){
			g[road[i].Y.X].push_back(MP(road[i].Y.Y, road[i].X));
			g[road[i].Y.Y].push_back(MP(road[i].Y.X, road[i].X));
		}
		else{
			need.push_back(i);
		}
	}
	for(int i = 1;i <= n;i++){
		if(comp[i])
			continue;
		comp[0]++;
		dfs(i);
	}
	for(int id: need){
		road[id].Y = MP(comp[road[id].Y.X], comp[road[id].Y.Y]);
	}
	for(int i = 1;i <= k;i++){
		gr[i].Y = MP(comp[gr[i].Y.X], comp[gr[i].Y.Y]);
	}
}

int prs[N], btn[N], dpt[N], chk[N];
ll szs[N];

void dfs2(int v, int pr){
	szs[v] = sz[v];
	for(pair<int, int> to: g[v]){
		if(to.X == pr)
			continue;
		chk[to.X] = to.Y;
		btn[to.X] = 1e9;
		prs[to.X] = v;
		dpt[to.X] = dpt[v] + 1;
		dfs2(to.X, v);
		szs[v] += szs[to.X];
	}
}

ll solve(int mask){
	ll res = 0;
	for(int i = 1;i <= comp[0];i++)
		g[i].clear();
	build(comp[0]);
	for(int i = 0;i < k;i++){
		if((mask >> i) & 1){
			if(!merge(gr[i + 1].Y.X, gr[i + 1].Y.Y))
				return 0;
			g[gr[i + 1].Y.X].push_back(MP(gr[i + 1].Y.Y, i + 1));
			g[gr[i + 1].Y.Y].push_back(MP(gr[i + 1].Y.X, i + 1));
		//	lims[i + 1] = N * 1ll * N;
		}
	}
	vector<int> need2;
	for(int id: need){
		if(merge(road[id].Y.X, road[id].Y.Y)){
			g[road[id].Y.X].push_back(MP(road[id].Y.Y, 0));
			g[road[id].Y.Y].push_back(MP(road[id].Y.X, 0));
		}
		else{
			need2.push_back(id);	
		}
	}
	dfs2(1, 1);
	for(int id: need2){
		pair<int, int> temp = road[id].Y;
		if(dpt[temp.X] < dpt[temp.Y])
			swap(temp.X, temp.Y);
		while(dpt[temp.X] > dpt[temp.Y]){
			btn[temp.X] = min(btn[temp.X], road[id].X);
			temp.X = prs[temp.X];
		}
		while(temp.X != temp.Y){
			btn[temp.X] = min(btn[temp.X], road[id].X);
			temp.X = prs[temp.X];
			btn[temp.Y] = min(btn[temp.Y], road[id].X);
			temp.Y = prs[temp.Y];
		}
	}
	for(int i = 2;i <= comp[0];i++){
		if(chk[i])
			res += szs[i] * btn[i];//, cerr << btn[i] << " s " << szs[i] << "\n";
	}
	return res;	
}

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
    cin >> n >> m >> k;
    for(int i = 1;i <= m;i++)
    	cin >> road[i].Y.X >> road[i].Y.Y >> road[i].X;
    for(int i = 1;i <= k;i++){
    	cin >> gr[i].Y.X >> gr[i].Y.Y;
	}
   	for(int i = 1;i <= n;i++){
   		cin >> p[i];
   	}
   	prep();
   	ll res = 0;
   	for(int i = 1;i < (1 << k);i++){
   		res = max(res, solve(i));
   	}
   	cout << res;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 4 ms 7424 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 4 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 7 ms 7552 KB Output is correct
6 Correct 7 ms 7552 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 4 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 7 ms 7552 KB Output is correct
6 Correct 7 ms 7552 KB Output is correct
7 Correct 235 ms 15852 KB Output is correct
8 Correct 241 ms 15864 KB Output is correct
9 Correct 232 ms 15864 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 4 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 7 ms 7552 KB Output is correct
6 Correct 7 ms 7552 KB Output is correct
7 Correct 235 ms 15852 KB Output is correct
8 Correct 241 ms 15864 KB Output is correct
9 Correct 232 ms 15864 KB Output is correct
10 Correct 1636 ms 15836 KB Output is correct
11 Correct 1995 ms 15904 KB Output is correct
12 Correct 1957 ms 15840 KB Output is correct