oj.uz

답안 #258731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258731 2020-08-06T12:55:16 Z pure_mem 통행료 (APIO13_toll) C++14
78 / 100
 2110 ms 22392 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;
 
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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Correct 11 ms 7680 KB Output is correct
6 Correct 8 ms 7680 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Correct 11 ms 7680 KB Output is correct
6 Correct 8 ms 7680 KB Output is correct
7 Correct 248 ms 22172 KB Output is correct
8 Correct 252 ms 22204 KB Output is correct
9 Correct 256 ms 22264 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Correct 11 ms 7680 KB Output is correct
6 Correct 8 ms 7680 KB Output is correct
7 Correct 248 ms 22172 KB Output is correct
8 Correct 252 ms 22204 KB Output is correct
9 Correct 256 ms 22264 KB Output is correct
10 Correct 1658 ms 22304 KB Output is correct
11 Correct 2082 ms 22392 KB Output is correct
12 Incorrect 2110 ms 22292 KB Output isn't correct