Submission #1291992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291992		dosts	통행료 (APIO13_toll)	C++20	16 / 100	2 ms	1088 KiB

toll

#include <bits/stdc++.h>
#ifdef Dodi
#include "/home/dodi/Desktop/ATC/ARC/arc156/debug.h"
#else
#define debug(...) void(42)
#endif
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e18;

const int N = 1e5+1;


struct DSU {
    vi dad;

    DSU(int nn) {
        dad.resize(nn+1);
        iota(all(dad),0ll);
    }
    int find(int x) {
        if (x == dad[x]) return x;
        return dad[x] = find(dad[x]);
    }

    void unite(int x,int y) {
        dad[find(x)] = find(y);
    }
};
vector<pair<pii,int>> final[N];
vi people(N);
pii dfs(int node,int p) {
    int ans = 0;
    int many = people[node];
    for (auto it : final[node]) {
        if (it.ff.ff == p) continue;
        pii pr = dfs(it.ff.ff,node);
        if (it.ff.ss) ans+=pr.ss*it.ss;
        ans+=pr.ff,many+=pr.ss;
    }
    return {ans,many};
}

void solve() {
    int n,m,k;
    cin >> n >> m >> k;
    vector<pair<int,pii>> edges;
    vector<pii> my_edges;
    for (int i=1;i<=m;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges.push_back({c,{a,b}});
    }
    for (int i=1;i<=k;i++) {
        int a,b;
        cin >> a >> b;
        my_edges.push_back({a,b});
    }
    for (int i=1;i<=n;i++) cin >> people[i];
    sort(all(edges));
    DSU dsu(n);
    for (auto [cost,con] : edges) {
        auto [a,b] = con;
        if (dsu.find(a) == dsu.find(b)) continue;
        int fl = 0;
        for (auto it : my_edges) {
            if (dsu.find(it.ff) == dsu.find(it.ss)) continue;
            int u = dsu.find(it.ff), v = dsu.find(it.ss);
            if (set<int>{dsu.find(a),dsu.find(b)} == set<int>{u,v}) {
                final[it.ff].push_back({{it.ss,1},cost});
                fl = 1;
                final[it.ss].push_back({{it.ff,1},cost});
                dsu.unite(it.ff,it.ss);
                break;
            }
        }
        if (!fl) {
            final[a].push_back({{b,0},cost});
            final[b].push_back({{a,0},cost});
            dsu.unite(a,b);
        }
    }
    cout << dfs(1,1).ff << '\n';
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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