Submission #909515

#	Time	Username	Problem	Language	Result	Execution time	Memory
909515		Faisal_Saqib	Toll (APIO13_toll)	C++17	16 / 100	2 ms	8796 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define pb push_back
#define int long long
using namespace std;
const int N=1e5+10;
int par[N],mx_sz=0,mx_we=0,ver=0;
pair<int,int> par1[N];
int h[N],sz1[N],val[N];
set<pair<int,int>> ma[N];
set<pair<int,int>> my_own;
int ans=0;
void dfs(int x,int p=-1)
{
    sz1[x]=val[x];
    for(auto [w,y]:ma[x])
    {
        if(y!=p)
        {
            dfs(y,x);
            sz1[x]+=sz1[y];
            if(my_own.find({x,y})!=my_own.end())
            {
                ans+=(w*sz1[y]);
            }
        }
    }
}
void root_at(int x,int p=-1)
{
    sz1[x]=val[x];
    for(auto [w,y]:ma[x])
    {
        if(y!=p)
        {
            h[y]=h[x]+1;
            par1[y]={w,x};
            root_at(y,x);
            sz1[x]+=sz1[y];
        }
    }
}
int root(int x)
{
    return (par[x]==x?x:par[x]=root(par[x]));
}
bool join(int x,int y)
{
    x=root(x);
    y=root(y);
    if(x!=y)
    {
        par[x]=y;
        return 1;
    }
    return 0;
}
signed main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        par[i]=i;
    vector<vector<int>> edg;
    for(int j=0;j<m;j++)
    {
        int w,x,y;
        cin>>x>>y>>w;
        edg.pb({w,x,y});
    }
    sort(begin(edg),end(edg));
    for(auto fp:edg)
    {
        if(join(fp[1],fp[2]))
        {
            ma[fp[1]].insert({fp[0],fp[2]});
            ma[fp[2]].insert({fp[0],fp[1]});
        }
    }
    vector<pair<int,int>> st;
    while(k--)
    {
        int x,y;
        cin>>x>>y;
        st.pb({x,y});
    }
    for(int i=1;i<=n;i++)
        cin>>val[i];
    for(auto [x,y]:st)
    {
        int x1=x;
        int y1=y;
        root_at(1);
        mx_sz=0;
        mx_we=-1e9;
        ver=-1;
        while(x!=y)
        {
            if(h[x]<h[y])
            {
                if(par1[y].first>mx_we)
                {
                    mx_we=par1[y].first;
                    mx_sz=sz1[y];
                    ver=y;
                }
                y=par1[y].second;
            }
            else
            {
                if(par1[x].first>mx_we)
                {
                    mx_we=par1[x].first;
                    mx_sz=sz1[x];
                    ver=x;
                }
                x=par1[x].second;
            }
        }
        // cout<<"Found "<<ver<<endl;
        ma[ver].erase(par1[ver]);
        ma[par1[ver].second].erase({par1[ver].first,ver});
        ma[x1].insert({mx_we,y1});
        ma[y1].insert({mx_we,x1});
        my_own.insert({x1,y1});
        my_own.insert({y1,x1});
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

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