Submission #511344

#	Time	Username	Problem	Language	Result	Execution time	Memory
511344		pokmui9909	Toll (APIO13_toll)	C++17	56 / 100	2554 ms	18224 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
   
#define x first
#define y second
class UnionFind{
public:
    UnionFind(ll S){
        p.resize(S + 5, -1);
    }
    void reset(){ fill(p.begin(), p.end(), -1); }
    void reset_small(){ 
        for(int i = 0; i < 35; i++){
            p[i] = -1;
        }
    }
    ll Find(ll n){ return (p[n] < 0 ? n : Find(p[n])); }
    void Union(ll a, ll b){
        a = Find(a), b = Find(b);
        if (a == b) return;
        p[b] += p[a];
        p[a] = b;
    }
    bool Same(ll a, ll b){ return Find(a) == Find(b); }
private:
    vector<ll> p;
};
ll N, M, K;
struct Edge{
    ll u, v, c;
    bool operator<(const Edge &r)const{
        return c < r.c;
    }
    bool operator==(const Edge &r)const{
        return u == r.u && v == r.v && c == r.c;
    }
};
vector<Edge> E;
vector<Edge> add;
ll P[100005];
struct MyStruct{
    ll n, c, f;
};
UnionFind S(100005);
vector<pair<ll, ll>> G[100005];
ll Par[100005];
ll depth[100005];
ll MinCost[100005];
ll cnt[100005];
vector<Edge> rem;
vector<ll> CG[100005];
vector<Edge> NE;
ll NP[100005];
ll num[100005];
ll check[35][35];
void dfs1(ll n, ll p){
    Par[n] = p;
    for(auto i : G[n]){
        if(i.x == p) continue;
        depth[i.x] = depth[n] + 1;
        dfs1(i.x, n);
    }
}
ll sum = 0;
void dfs2(ll n, ll p){
    cnt[n] = NP[n];
    for(auto i : G[n]){
        ll nx = i.x, c = i.y;
        if(nx == p) continue;
        dfs2(nx, n);
        cnt[n] += cnt[nx];
        if(c == -1){
            sum += MinCost[nx] * cnt[nx];
        }
    }
}
 
void init(){
    for(int i = 0; i < 35; i++){
        for(int j = 0; j < 35; j++){
            check[i][j] = 1e18;
        }
    }
    for(int i = 0; i < K; i++){
        ll u = add[i].u, v = add[i].v;
        S.Union(u, v);
    }
    for(int i = 0; i < M; i++){
        ll u = E[i].u, v = E[i].v, c = E[i].c;
        if(S.Same(u, v)){
            rem.push_back({u, v, c});
        } else {
            CG[u].push_back(v);
            CG[v].push_back(u);
            S.Union(u, v);
        }
    }
    ll Comps = 0;
    for(int i = 1; i <= N; i++){
        if(num[i]) continue;
        queue<ll> Q;
        Q.push(i);
        Comps++;
        num[i] = Comps;
        while(!Q.empty()){
            ll t = Q.front(); Q.pop();
            NP[Comps] += P[t];
            for(auto j : CG[t]){
                if(num[j]) continue;
                num[j] = Comps;
                Q.push(j);
            }
        }
    }
    for(int i = 0; i < rem.size(); i++){
        ll u = rem[i].u, v = rem[i].v, c = rem[i].c;
        if(num[u] == num[v]) continue;
        if(num[u] > num[v]) swap(u, v);
        if(check[num[u]][num[v]] > c){
            check[num[u]][num[v]] = c;
        }
    }
    for(int i = 1; i < 35; i++){
        for(int j = i + 1; j < 35; j++){
            if(check[i][j] >= 1e18) continue;
            NE.push_back({i, j, check[i][j]});  
        }
    }
    sort(NE.begin(), NE.end());
    for(int i = 0; i < add.size(); i++){
        add[i].u = num[add[i].u];
        add[i].v = num[add[i].v];
    }
    assert(Comps <= 30);
}
 
ll Solve(vector<ll> Plus){
    S.reset_small();
    for(int i = 0; i < 35; i++){
        G[i].clear();
        MinCost[i] = 1e18;
    }
    for(auto i : Plus){
        ll u = add[i].u, v = add[i].v;
        if(S.Same(u, v)) return -1;
        S.Union(u, v);
        G[u].push_back({v, -1});
        G[v].push_back({u, -1});
    }
    for(int i = 0; i < NE.size(); i++){
        ll u = NE[i].u, v = NE[i].v, c = NE[i].c;
        if(S.Same(u, v)) continue;
        S.Union(u, v);
        G[u].push_back({v, c});
        G[v].push_back({u, c});
    }
    dfs1(1, -1);
    for(int i = 0; i < NE.size(); i++){
        ll u = NE[i].u, v = NE[i].v, c = NE[i].c;
        if(depth[u] < depth[v]) swap(u, v);
        while(depth[u] != depth[v]){
            MinCost[u] = min(MinCost[u], c);
            u = Par[u];
        }
        while(u != v){
            MinCost[u] = min(MinCost[u], c);
            MinCost[v] = min(MinCost[v], c);
            u = Par[u];
            v = Par[v];
        }
    }
    sum = 0;
    dfs2(1, -1);
    return sum;
}
   
int main(){
    cin.tie(0) -> sync_with_stdio(false);
    
    cin >> N >> M >> K;
    for(int i = 1; i <= M; i++){
        ll u, v, c; cin >> u >> v >> c;
        E.push_back({u, v, c});
    }
    for(int i = 1; i <= K; i++){
        ll u, v; cin >> u >> v;
        add.push_back({u, v});
    }
    for(int i = 1; i <= N; i++){
        cin >> P[i];
    }
    sort(E.begin(), E.end());
    init();
    ll ans = 0;
    for(int i = 0; i < (1 << K); i++){
        vector<ll> Plus;
        for(int j = 0; j < K; j++){
            if(i & (1 << j)){
                Plus.push_back(j);
            }
        }
        ans = max(ans, Solve(Plus));
    }
    cout << ans;
}

Compilation message (stderr)

toll.cpp: In function 'void init()':
toll.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int i = 0; i < rem.size(); i++){
      |                    ~~^~~~~~~~~~~~
toll.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for(int i = 0; i < add.size(); i++){
      |                    ~~^~~~~~~~~~~~
toll.cpp: In function 'll Solve(std::vector<long long int>)':
toll.cpp:151:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int i = 0; i < NE.size(); i++){
      |                    ~~^~~~~~~~~~~
toll.cpp:159:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(int i = 0; i < NE.size(); i++){
      |                    ~~^~~~~~~~~~~

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