Submission #1155562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155562		NeilP	Toll (APIO13_toll)	C++20	16 / 100	0 ms	324 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>
using std::pair;
using std::vector;
using std::cout;
using std::cin;
using std::endl;
using std::endl;
using std::swap;

struct Edge{
    long long a;
    long long b;
    long long cost;
};

long long n, m, k;
vector<vector<pair<long long, long long>>> tree;

bool comp(Edge a, Edge b){
    return a.cost < b.cost;
}

vector<long long> parent;
vector<long long> size;
vector<long long> tots;
vector<long long> parent2;
vector<long long> size2;

long long find(long long x){
    if(parent[x] == x)
        return x;
    else
    {
        return (parent[x] = find(parent[x]));
    }
}

long long find2(long long x){
    if(parent2[x] == x)
        return x;
    else
    {
        return (parent2[x] = find2(parent2[x]));
    }
}

void merge(long long x, long long y){
    long long xh = find(x);
    long long yh = find(y);
    if(xh == yh)
        return;
    if(size[xh] > size[yh])
        swap(xh, yh);
    parent[xh] = yh;
    size[yh] += size[xh];
}

void merge2(long long x, long long y){
    long long xh = find2(x);
    long long yh = find2(y);
    if(xh == yh)
        return;
    if(size2[xh] > size2[yh])
        swap(xh, yh);
    parent2[xh] = yh;
    size2[yh] += size2[xh];
}

pair<long long, long long> dfs(long long x, long long p) // (size, money)
{
    pair<long long, long long> tot = {tots[x], 0};
    for(pair<long long, long long> q: tree[x]){ // (neighboor, cost)
        if(q.first == p){
            continue;
        }
        pair<long long, long long> res = dfs(q.first, x);
        tot.first += res.first;
        tot.second += 1LL * q.second * res.first + res.second;
    }
    return tot;
}

int main()
{
    cin >> n >> m >> k;
    
    for(long long i = 0; i < n; i++){
        parent.push_back(i);
        size.push_back(1);
        parent2.push_back(i);
        size2.push_back(1);
    }
    
    long long start[20], end[20], toll[20];
    
    vector<Edge> edges;
    for(long long i = 0; i < m; i++){
        long long u, v, c;
        cin >> u >> v >> c;
        u--;
        v--;
        Edge e = {u, v, c};
        edges.push_back(e);
    }
    sort(edges.begin(), edges.end(), comp);
    
    for(long long i = 0; i < k; i++){
        cin >> start[i] >> end[i];
        start[i]--;
        end[i]--;
        toll[i] = 0;
    }
    
    tots = vector<long long>(n);
    for(long long i = 0; i < n; i++){
        cin >> tots[i];
    }    
    
    tree = vector<vector<pair<long long, long long>>>(n);
    bool useful[20]; // Records if this would be necessary before new roads
    int ei = 0;
    while(ei < edges.size()){
        for(int i = 0; i < k; i++){
            if(find2(start[i]) != find2(end[i])){ // using second DSU
                useful[i] = true;
            }else{
                useful[i] = false;
            }
        }
        long long ref = edges[ei].cost;
        int st = ei;
        
        while(ei < edges.size() && ref == edges[ei].cost){
            merge2(edges[ei].a, edges[ei].b); // using second DSU to keep track
            ei++; // Next edge
        }
        
        for(int i = 0; i < k; i++){
            if(useful[i] && find2(start[i]) == find2(end[i])){ // Threatened by new edges
                if(find(start[i]) != find(end[i])) // if Threatened by own toll, give up
                {
                    merge(start[i], end[i]);
                    tree[start[i]].push_back({end[i], ref});
                    tree[end[i]].push_back({start[i], ref});
                }
            }   
        }
        
        for(int i = st; i < ei; i++){
            if(find(edges[i].a) != find(edges[i].b)){
                tree[edges[i].a].push_back({edges[i].b, 0});
                tree[edges[i].b].push_back({edges[i].a, 0});
                merge(edges[i].a, edges[i].b);
            }
        }
    }
    pair<long long, long long> res = dfs(0, -1);
    cout << res.second << endl;
    

    return 0;
}

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