Submission #1095894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095894		lighton	Toll (APIO13_toll)	C++17	56 / 100	439 ms	25468 KiB

toll

#include<bits/stdc++.h>
#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){
        int subs = dfs(nxt,now);
        if(ind > M) ans += cost[ind-M]*subs;
        s += subs;
    }
    return s;
}
int upd(int now, int p, int goal, ll w){
    if(now == goal) return 1;
    int ret = 0;
    for(auto [nxt,ind] : adj[now]) if(nxt!=p){
        if(upd(nxt,now,goal,w) == 1){
            ret = 1;
            if(ind > M) cost[ind-M] = min(cost[ind-M], w);
        }
    }
    return ret;
}

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(ngrp[u] != ngrp[v]){
            
            if(m.find({ngrp[u],ngrp[v]}) == m.end()) cross.pb(ind), m.insert({ngrp[u],ngrp[v]});
        }
        if(dsu1.fi(u) != dsu1.fi(v)){
            dsu1.un(u,v);
            
        }
    }

    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;
        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});
            }
        }
        
        for(int ind : cross){
            int u = ngrp[edges[ind][0]], v= ngrp[edges[ind][1]];
            ll w = edges[ind][2];
            auto trash = upd(u,-1,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:122:18: warning: unused variable 'trash' [-Wunused-variable]
  122 |             auto trash = upd(u,-1,v,w);
      |                  ^~~~~
toll.cpp:126:14: warning: unused variable 'realtrash' [-Wunused-variable]
  126 |         auto realtrash = dfs(ngrp[1],-1);
      |              ^~~~~~~~~

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