Submission #1095931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095931		lighton	Toll (APIO13_toll)	C++17	78 / 100	2529 ms	21736 KiB

toll

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 2e9;
ll N,M,K;
array<ll,3> edges[400001];
struct DSU{
    int grp[200001];
    void init(int n){forf(i,1,n) grp[i] = i;}
    int fi(int x){
        if(grp[x] == x) return x;
        return grp[x] = fi(grp[x]);
    }
    void un(int x, int y){
        x = fi(x), y = fi(y);
        grp[x] = y;
    }
} dsu1, dsu2;
ll S[200001];

int grpnum = 1;
int ngrp[200001],ngrpchk[200001];
ll siz[51];

ll cost[51];
vector<int> cross;
vector<pair<int,int> > adj[51];
ll ans;
ll dfs(int now, int p){
    ll s = siz[now];
    for(auto [nxt,ind] :adj[now]) if(nxt!=p){
        ll subs = dfs(nxt,now);

        if(ind > M) ans += cost[ind-M]*subs;
        s += subs;
    }
    return s;
}

void upd(int now, int goal, ll w){
    queue<int> q;
    vector<pair<int,int> > par(grpnum+1,{-1,-1});
    par[now] = {now,0}; q.push(now);
    while(q.size()){
        int cur = q.front(); q.pop();
        if(cur == goal) break;
        for(auto [i,ind] : adj[cur]){
            if(par[i].fs == -1){
                par[i] = {cur,ind};
                q.push(i);
            }
        }
    }
    
    for(int i = goal; i != par[i].fs; i = par[i].fs){
        if(par[i].se > M){
            cost[par[i].se-M] = min(w,cost[par[i].se-M]);
        }
    }
}

int main(){
    cin>>N>>M>>K;
    vector<pair<ll,int> > allg,org;
    forf(i,1,M) cin>>edges[i][0]>>edges[i][1]>>edges[i][2], allg.pb({edges[i][2], i}) ,org.pb({edges[i][2], i});
    forf(i,1,K) cin>>edges[M+i][0]>>edges[M+i][1], allg.pb({0, M+i});
    forf(i,1,N) cin>>S[i];
    sort(all(allg)), sort(all(org));
    dsu1.init(N),dsu2.init(N);
    for(auto [c,ind] : allg){
        int u = edges[ind][0], v = edges[ind][1];
        if(dsu1.fi(u) != dsu1.fi(v)){
            dsu1.un(u,v);
            if(c!=0) dsu2.un(u,v);
        }
    }

    forf(i,1,N){
        if(ngrpchk[dsu2.fi(i)] == 0) ngrpchk[dsu2.fi(i)] = grpnum, grpnum++;
        ngrp[i] = ngrpchk[dsu2.fi(i)];
        siz[ngrp[i]]+=S[i];
    }
    grpnum--;
    assert(grpnum <= K+1);

    set<pair<int,int> > m;
    dsu1.init(N);
    for(auto [c,ind] : org){
        int u = edges[ind][0], v = edges[ind][1];
        if(dsu1.fi(u) != dsu1.fi(v)){
            dsu1.un(u,v);
            if(ngrp[u] != ngrp[v]) cross.pb(ind), m.insert({ngrp[u],ngrp[v]});
        }
    }
    assert(sz(cross) <= K);

    ll rans=0;
    forf(bit,0,(1<<K)-1){
        forf(i,1,grpnum) adj[i].clear();
        forf(i,1,K) cost[i] = inf;
        dsu1.init(grpnum);

        vector<pair<ll,int> > g;
        vector<int> nc;
        for(int i :cross) g.pb({edges[i][2], i});
        forf(i,1,K) if(bit & (1<<(i-1))) g.pb({0, M+i});

        sort(all(g));
        for(auto [c,ind] : g){
            int u = ngrp[edges[ind][0]], v= ngrp[edges[ind][1]];
            assert(u!=v);
            if(dsu1.fi(u) != dsu1.fi(v)){
                dsu1.un(u,v);
                adj[u].pb({v,ind}), adj[v].pb({u,ind});
            }
            else if(ind <= M) nc.pb(ind);
        }
        for(int ind : nc){
            int u = ngrp[edges[ind][0]], v= ngrp[edges[ind][1]];
            ll w = edges[ind][2];
            upd(u,v,w);
        }

        ans = 0;
        auto realtrash = dfs(ngrp[1],-1);
        rans = max(ans,rans);
    }
    cout<<rans;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:141:14: warning: unused variable 'realtrash' [-Wunused-variable]
  141 |         auto realtrash = dfs(ngrp[1],-1);
      |              ^~~~~~~~~

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