Submission #1110803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110803		mariaclara	Toll (APIO13_toll)	C++17	16 / 100	2 ms	4944 KiB

toll

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef tuple<int,int,int> trio;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
const ll INF = 1e9;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

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

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 pai) {
    ll sum = p[x];

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

    return sum;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    
    cin >> n >> m >> k;

    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.pb({c,a,b});
    }

    sort(all(edges));

    for(int i = 1; i <= k; i++) 
        cin >> A[i] >> B[i];

    for(int i = 1; i <= n; i++)
        cin >> p[i], pai[i] = i;

    for(auto [cost, u, v] : edges) {
        bool ok = join(u,v);
        if(!ok) continue;

        for(int i = 1; i <= k; i++) {
            if(!used[i] and find(A[i]) == find(B[i])) {
                used[i] = 1;
                if(ok) graph[A[i]].pb({B[i], cost, 1}), graph[B[i]].pb({A[i], cost, 1}), ok = 0;
            }
        }

        if(ok) graph[u].pb({v, cost, 0}), graph[v].pb({u, cost, 0});
    }

    dfs(1, 0);

    cout << ans << "\n";
}

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