oj.uz

Submission #1095943

# Submission time Handle Problem Language Result Execution time Memory
1095943 2024-10-03T12:21:26 Z lighton Toll (APIO13_toll) C++17
100 / 100
 1252 ms 25604 KB 
#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){
            ll 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(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});
        int cnt=0;
        forf(i,1,K) if(bit & (1<<(i-1))) g.pb({0, M+i}),cnt++;
        if(cnt<K-8) continue;
        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];
            auto trash = upd(u,-1,v,w);
        }

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

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:123:18: warning: unused variable 'trash' [-Wunused-variable]
  123 |             auto trash = upd(u,-1,v,w);
      |                  ^~~~~
toll.cpp:127:14: warning: unused variable 'realtrash' [-Wunused-variable]
  127 |         auto realtrash = dfs(ngrp[1],-1);
      |              ^~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 308 ms 18932 KB Output is correct
8 Correct 319 ms 19100 KB Output is correct
9 Correct 322 ms 19104 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 308 ms 18932 KB Output is correct
8 Correct 319 ms 19100 KB Output is correct
9 Correct 322 ms 19104 KB Output is correct
10 Correct 959 ms 19104 KB Output is correct
11 Correct 1236 ms 19104 KB Output is correct
12 Correct 1252 ms 25604 KB Output is correct