oj.uz

Submission #873524

# Submission time Handle Problem Language Result Execution time Memory
873524 2023-11-15T08:58:05 Z gggkik Toll (APIO13_toll) C++14
56 / 100
 2500 ms 25840 KB 
#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e5+5;
using pii = pair<int,int>;
using ll = long long;
struct EDGES{int a,b,c;};
bool operator<(const EDGES &i, const EDGES &j){
    return tie(i.a,i.b,i.c)<tie(j.a,j.b,j.c);
}
struct dsu{
    vector<int> par;
    void init(int x){
        par.resize(x+1);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        return par[x]-x?par[x]=find(par[x]):x;
    }
    void u(int a,int b){
        a = find(a), b = find(b);
        if(a!=b) par[a] = b;
    }
};
vector<EDGES> build_mst(int n, vector<EDGES> edges){
    dsu uf; uf.init(n);
    vector<EDGES> ret;
    for(auto &i : edges){
        int a = uf.find(i.a), b = uf.find(i.b);
        if(a!=b) {
            uf.u(a,b); 
            ret.push_back(i);
        }
    }
    return ret;
}
vector<pii> E[MXN];
ll A[MXN], sz[MXN], val[MXN];
int h[MXN], par[MXN];
void pre(int x,int p){
    par[x] = p;
    h[x] = h[p]+1;
    for(auto &i : E[x]) if(i.first!=p)
        pre(i.first,x);
}
pair<ll,ll> get(int x,int p){
    pair<ll,ll> ret = {sz[x],0};
    for(auto &i : E[x]) if(i.first!=p){
        pair<ll,ll> r = get(i.first,x);
        ret.first += r.first;
        ret.second += r.second;
        if(!i.second) ret.second += val[i.first]*r.first;
    }
    return ret;
}
dsu mov;
void lca(int a,int b,ll c){
    while(a!=b){
        if(h[a]<h[b]) swap(a,b);
        val[a] = min(val[a],c);
        mov.u(a,par[a]);
        a = mov.find(par[a]);
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, k; cin >> n >> m >> k;
    vector<EDGES> edges;
    for(int i = 0;i<m;i++){
        int a,b,c; cin >> a >> b >> c;
        edges.push_back({a,b,c});
    }
    sort(edges.begin(),edges.end(),[&](EDGES &i, EDGES &j){
        return i.c<j.c;
    });
    vector<EDGES> myedge;
    for(int i = 0;i<k;i++){
        int a,b; cin >> a >> b;
        myedge.push_back({a,b,0});
    }
    for(int i = 1;i<=n;i++) {
        cin >> A[i];
    }
    map<EDGES,int> EDGE;

    vector<EDGES> tmp = build_mst(n, edges);
    for(auto &i : tmp) EDGE[i]++;

    tmp = myedge; 
    for(auto &i : edges) tmp.push_back(i);
    tmp = build_mst(n, tmp);
    for(auto &i : tmp) EDGE[i]++;

    dsu king; 
    king.init(n);
    for(auto &j : EDGE)if(j.second==2){
        EDGES i = j.first;
        king.u(i.a,i.b);
    }
    vector<int> kingv, kf(n+1);
    for(int i = 1;i<=n;i++){
        kf[i] = king.find(i);
        sz[kf[i]] += A[i];
        if(kf[i]==i) kingv.push_back(i);
    }
    vector<EDGES> real;
    for(auto &i : edges) {
        if(king.find(i.a)!=king.find(i.b)) real.push_back(i);
    }
    assert(kingv.size()<=3*k+3);
    ll ans = 0;
    dsu uf; uf.init(n); mov.init(n);
    for(int mask = 0;mask<1<<k;mask++){
        for(auto &i : kingv) {
            uf.par[i] = i;
            mov.par[i] = i;
            val[i] = 1LL<<62;
            E[i].clear();
        }
        for(int i = 0;i<k;i++)if(mask>>i&1){
            int u = kf[myedge[i].a], v = kf[myedge[i].b];
            if(uf.find(u)==uf.find(v)) continue;
            uf.u(u,v);
            E[u].push_back({v,0});
            E[v].push_back({u,0});
        }
        vector<EDGES> NO;
        for(auto &i : real){
            int a = kf[i.a], b = kf[i.b];
            if(uf.find(a)==uf.find(b)) {
                NO.push_back({a,b,i.c});
                continue;
            }
            uf.u(a,b);
            E[a].push_back({b,i.c});
            E[b].push_back({a,i.c});
        }
        pre(king.find(1),0);
        for(auto &i : NO) lca(i.a,i.b,i.c);
        ll cost = get(king.find(1),0).second;
        ans = max(ans,cost);
    }
    cout << ans;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from toll.cpp:1:
toll.cpp: In function 'int main()':
toll.cpp:109:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |     assert(kingv.size()<=3*k+3);
      |            ~~~~~~~~~~~~^~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 3 ms 5720 KB Output is correct
4 Correct 2 ms 5784 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 3 ms 5720 KB Output is correct
4 Correct 2 ms 5784 KB Output is correct
5 Correct 22 ms 5972 KB Output is correct
6 Correct 51 ms 6224 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 3 ms 5720 KB Output is correct
4 Correct 2 ms 5784 KB Output is correct
5 Correct 22 ms 5972 KB Output is correct
6 Correct 51 ms 6224 KB Output is correct
7 Execution timed out 2524 ms 25840 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 1 ms 5720 KB Output is correct
3 Correct 3 ms 5720 KB Output is correct
4 Correct 2 ms 5784 KB Output is correct
5 Correct 22 ms 5972 KB Output is correct
6 Correct 51 ms 6224 KB Output is correct
7 Execution timed out 2524 ms 25840 KB Time limit exceeded
8 Halted 0 ms 0 KB -