Submission #742808

#	Time	Username	Problem	Language	Result	Execution time	Memory
742808		victor_gao	Toll (APIO13_toll)	C++17	16 / 100	3 ms	5044 KiB

toll

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,k,m,cost[30],fa[N],sz[N],ans=0;
pii dp[N];
set<pii>g[N];
vector<pair<int,pii> >edge,add;
struct DSU{
    int boss[N],sz[N];
    void init(int n){
        for (int i=1;i<=n;i++){
            boss[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        if (boss[x]==x) return x;
        return boss[x]=find(boss[x]);
    }
    void merge(int a,int b){
        int ra=find(a),rb=find(b);
        if (ra==rb) return;
        if (sz[ra]<sz[rb]) swap(ra,rb);
        sz[ra]+=sz[rb];
        boss[rb]=ra;
    }
}d;
void dfs(int p,int lp,int c){
    dp[p]=max(dp[lp],pii(c,p));
    fa[p]=lp;
    for (auto i:g[p]){
        if (i.x!=lp)
            dfs(i.x,p,i.y);
    }
}
void dfs1(int p,int lp){
    for (auto i:g[p]){
        if (i.x!=lp){
            dfs1(i.x,p);
            ans=(ans+sz[i.x]*i.y);
            sz[p]+=sz[i.x];
        }
    }
}
signed main(){
    fast
    cin>>n>>m>>k;
    for (int i=1;i<=m;i++){
        int a,b,c; cin>>a>>b>>c;
        edge.push_back({c,{a,b}});
    }
    sort(edge.begin(),edge.end());
    d.init(n);
    for (auto [c,tmp]:edge){
        auto [a,b]=tmp;
        if (d.find(a)!=d.find(b)){
            d.merge(a,b);
            g[a].insert({b,c});
            g[b].insert({a,c});
        }
    }
    for (int i=1;i<=k;i++){
        int a,b; cin>>a>>b;
        dfs(a,0,0);
        if (dp[b].x==0) continue;
        else {
            int p=dp[b].y;
            g[p].erase(pii(fa[p],dp[b].x));
            g[fa[p]].erase(pii(p,dp[b].x));
            g[a].insert({b,0});
            g[b].insert({a,0});
            cost[i]=dp[b].x;
            add.push_back({cost[i],{a,b}});
        }
    }
    for (int i=1;i<=n;i++)
        g[i].clear();
    d.init(n);
    for (auto [c,tmp]:add){
        auto [a,b]=tmp;
        if (d.find(a)!=d.find(b)){
            d.merge(a,b);
            g[a].insert({b,c});
            g[b].insert({a,c});
        }
    }
    for (auto [c,tmp]:edge){
        auto [a,b]=tmp;
        if (d.find(a)!=d.find(b)){
            d.merge(a,b);
            g[a].insert({b,0});
            g[b].insert({a,0});
        }
    }
    for (int i=1;i<=n;i++)
        cin>>sz[i];
    dfs1(1,0);
    cout<<ans<<'\n';
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/

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