Submission #909368

#	Time	Username	Problem	Language	Result	Execution time	Memory
909368		Jawad_Akbar_JJ	Toll (APIO13_toll)	C++17	16 / 100	10 ms	6492 KiB

toll

#include <iostream>
#include <set>
#include <vector>

using namespace std;
#define int long long
const int N = 1e5 +10;
vector<pair<int,int>> nei[N];
int u[N];
int v[N];
int w[N];
int p[N];
int par[N];
int n,k,m;
int ans = 0;
int Ans = 0;

int dfs(int u,int pp = -1){
    int pop = 0;
    for (auto [i,kk] : nei[u]){
        if (i==pp)
            continue;
        int a = dfs(i,u);
        pop += a;
        ans += kk * a;
    }
    return pop + p[u];
}



int root(int v){
    if (par[v]==-1)
        return v;
    par[v] = root(par[v]);
    return par[v];
}

void do_mst(int mask){

    for (int i=1;i<=n;i++)
        par[i] = -1,nei[i].clear();

    set<vector<int>> s;
    for (int i=1;i<=m;i++)
        s.insert({w[i],v[i],u[i]});
    
    while (s.size()>0){
        vector<int> a = *begin(s);
        s.erase(begin(s));
        int v1 = root(a[1]);
        int v2 = root(a[2]);
        // cout<<v1<<" jjjjjj "<<v2<<" "<<a[1]<<" "<<a[2]<<endl;

        if (v1 == v2){
            // cout<<v1<<" jj "<<v2<<" "<<a[1]<<" "<<a[2]<<endl;
            continue;
        }
        int kk = a[0];
        a[0] = 0;
        for (int i=0;i<k;i++)
            if ((1<<i)&mask){
                int v3 = root(nei[0][i].first);
                int v4 = root(nei[0][i].second);
                if ((v1 == v3 and v2 == v4) or (v1 == v4 and v2 == v3)){
                    a[1] = nei[0][i].first,a[2] = nei[0][i].second,a[0] = kk;
                    // cout<<v1<<" jj "<<v2<<" "<<v3<<" "<<v4<<endl;
                }
            }
        // cout<<a[1]<<" hhh "<<a[2]<<endl;
        nei[a[1]].push_back({a[2],a[0]});
        nei[a[2]].push_back({a[1],a[0]});
        par[v1] = v2;
    }
    ans = 0;
    dfs(1);
    Ans = max(Ans,ans);
}


signed main(){
    cin>>n>>m>>k;

    for (int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        u[i] = a;
        v[i] = b;
        w[i] = c;
    }

    for (int i=1;i<=k;i++){
        int a,b;
        cin>>a>>b;
        nei[0].push_back({a,b});
    }

    for (int i=1;i<=n;i++)
        cin>>p[i];

    for (int mask = 1;mask<(1<<k);mask++){
        do_mst(mask);
    }
    cout<<Ans<<endl;

}


// 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