제출 #258731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258731		pure_mem	통행료 (APIO13_toll)	C++14	78 / 100	2110 ms	22392 KiB

toll

#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;
 
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;
   //	cerr << comp[0] << endl;
   	for(int i = 1;i < (1 << k);i++){
   		res = max(res, solve(i));
 //  		cerr << "\n";
   	}
   	cout << res;
}

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