제출 #744958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744958		victor_gao	통행료 (APIO13_toll)	C++17	16 / 100	3 ms	5076 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],dep[N],isnew[N];
int dp1[(1<<20)+5],val[30][30],ans=0;
pii dp[N];
set<pii>g[N];
vector<pair<int,pii> >edge,out;
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,int c){
    fa[p]=lp; dep[p]=dep[lp]+1;
    if (c>=0) isnew[p]=c;
    for (auto [i,id]:g[p]){
        if (i!=lp){
            dfs1(i,p,-id);
            sz[p]+=sz[i];
        }
    }
}
void jump(int a,int b,int num,int c){
    while (a!=b){
        if (dep[a]<dep[b]) swap(a,b);
        if (isnew[a]>=0){
            val[isnew[a]][num]=sz[a]*c;
        }
        a=fa[a];
    }
}
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=0;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,-i});
            g[b].insert({a,-i});
            cost[i]=dp[b].x;
            out.push_back({dp[b].x,{p,fa[p]}});
        }
    }
    for (int i=1;i<=n;i++){
        cin>>sz[i];
        isnew[i]=-1;
    }
    dfs1(1,0,-1);
    for (int i=0;i<=k;i++)
        for (int j=0;j<=k;j++)
            val[i][j]=-1e9;
    k=out.size();
    for (int i=0;i<k;i++)
        jump(out[i].y.x,out[i].y.y,i,out[i].x);
    /*
    for (int i=0;i<k;i++){
        for (int j=0;j<k;j++)
            cout<<val[i][j]<<" ";
        cout<<'\n';
    }
    */
    for (int i=0;i<k;i++){
        for (int j=0;j<(1LL<<k);j++){
            for (int l=0;l<k;l++){
                if (j&(1LL<<l))
                    dp1[j]=max(dp1[j],dp1[j^(1LL<<l)]+val[i][l]);
            }
        }
    }
    cout<<dp1[(1LL<<k)-1]<<'\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