oj.uz

Submission #1095913

# Submission time Handle Problem Language Result Execution time Memory
1095913 2024-10-03T11:53:35 Z lighton Toll (APIO13_toll) C++17
78 / 100
 2500 ms 25728 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]});
        }
    }

    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

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

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 6 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 317 ms 25444 KB Output is correct
8 Correct 328 ms 25472 KB Output is correct
9 Correct 314 ms 25352 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 317 ms 25444 KB Output is correct
8 Correct 328 ms 25472 KB Output is correct
9 Correct 314 ms 25352 KB Output is correct
10 Correct 2061 ms 25728 KB Output is correct
11 Execution timed out 2520 ms 25480 KB Time limit exceeded
12 Halted 0 ms 0 KB -