Submission #1165235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165235		1a2b3c4d	Toll (APIO13_toll)	C++20	16 / 100	115 ms	229376 KiB

toll

#include <bits/stdc++.h>
using namespace std;
	
#define all(x) begin(x), end(x)
typedef long long ll;
#define int ll
 
const char nl = '\n';
const int N = 1e5+5;
const int inf = 1e8+10;
//const int mod = 1e9*5e5+10;

int n, m, k, p[N], pai[N];
int A[25], B[25], used[25];
ll ans;
vector<tuple<int,int,int>> edges;
vector<tuple<int,int,int>> graph[N];

int find(int x) {
    if(x == pai[x]) return x;
    return pai[x] = find(pai[x]);
}

bool join(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) return 0;
    pai[x] = y;

    return 1;
}

ll dfs(int x, int pa) {
    ll sum = p[x];

    for(auto [viz, cost, flag] : graph[x]) {
        if(viz == pa) continue;
        ll s_viz = dfs(viz, x);
        ans += s_viz * cost * flag;
        sum += s_viz;
    }

    return sum;
}
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
		int a, b, w;
		cin >> a >> b >> w;
		edges.push_back({w, a, b});
	} 
	
	sort(all(edges));
	for (int i = 0; i < k; ++i)cin >> A[i] >> B[i];
	
	for (int i = 1; i <= n; ++i){cin >> p[i]; pai[i] = i; }
	
	for (auto [w, a, b]: edges) {
		if (!join(a, b))continue;
		
		bool done = false;
		for (int i = 0; i < k; ++i) {
			if (used[i] == 0 && find(A[i]) == find(B[i])) {
				done = true, used[i] = 1;
				graph[A[i]].push_back({B[i], w, 1});
				graph[B[i]].push_back({A[i], w, 1});
				//cout << A[i] << " " << B[i] << " " << w << nl;
				break;
			}
		}
		
		if (!done)graph[a].push_back({b, w, 0}), graph[b].push_back({a, w, 0});
	}
	
	dfs(1, 1);
	cout << ans;
	return 0;
}

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