Submission #680978

#	Time	Username	Problem	Language	Result	Execution time	Memory
680978		vjudge1	Toll (APIO13_toll)	C++17	0 / 100	3 ms	4948 KiB

toll

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define endl '\n'
#define int long long
#define all(a) a.begin(),a.end()
#define pb push_back
#define mod 1000000007
#define inf 1e18
#define ppb pop_back
#define ff first
#define ss second
 
///  order_of_key return number of elements less than x -> os.order_of_key(x)
///  cout << "oth element  : " << *os.find_by_order(0) << endl; so it returns value of index
 
int lcm(int x,int y)
{
    return (x * 1LL * y) / __gcd(x,y);
}
 
// Graph on 2D Grid
/*----------------------Graph Moves----------------*/
//const int dx[]={+1,-1,+0,+0};
//const int dy[]={+0,+0,+1,-1};
//const int dx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int dy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int dx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int dy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/
 
#define debug(x); cerr << #x <<" "; _print(x); cerr << endl;
 
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
 
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
const int N=2e5+4;
int par[N],ar[N],cnt[N];
vector<pair<int,int> >v[N];
int find(int a)
{
    if(a==par[a])
    {
        return a;
    }
    return par[a]=find(par[a]);
}
void dfs(int a,int p)
{
    for(auto b:v[a])
    {
        if(b.first!=p)
        {
            dfs(b.first,a);
            ar[a]+=ar[b.first];
        }
    }
}
void dfs1(int a,int p,int val)
{
    cnt[a]=val;
    for(auto b:v[a])
    {
        if(b.first!=p)
        {
            dfs1(b.first,a,max(val,b.second));
        }
    }
}
void solve()
{
    int n,i,m,k,a,b,c,d;
    cin>>n>>m>>k;
    vector<pair<int,pair<int,int> > >v1;
    vector<pair<int,int> >v2;
    for(i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        v1.push_back({c,{a,b}});
    }
    for(i=0;i<k;i++)
    {
        cin>>a>>b;
        v2.push_back({a,b});
    }
    for(i=1;i<=n;i++)
    {
        cin>>ar[i];
    }
    for(i=1;i<=n;i++)
    {
        par[i]=i;
    }
    sort(v1.begin(),v1.end());
    for(i=0;i<m;i++)
    {
        a=v1[i].second.first;
        b=v1[i].second.second;
        c=find(a);
        d=find(b);
        if(c!=d)
        {
            par[c]=d;
            v[a].push_back({b,v1[i].first});
            v[b].push_back({a,v1[i].first});
        }
    }
    dfs(1,-1);
    int ans=0;
    for(i=0;i<k;i++)
    {
        a=v2[i].first;
        b=v2[i].second;
        dfs1(a,-1,0);
        ans+=(cnt[b]*min(ar[a],ar[b]));
    }
    cout<<ans<<endl;
}
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int t=1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}
/**
Test Case :
 
**/

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