Submission #1225234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225234		Bui_Quoc_Cuong	Toll (APIO13_toll)	C++20	100 / 100	870 ms	22092 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 3e5 + 5;

int n, m, k;
struct Edges{
    int u, v, w; 
} MST[MAX], SE[MAX], E[MAX];
int c[MAX];

vector <int> g[MAX];
int weight[MAX], par[MAX], h[MAX];
int sz[MAX];
int lab[MAX];
vector <array <int, 3>> edges;
bool in_MST[MAX];

int find(int x){
    return lab[x] < 0 ? x : lab[x] = find(lab[x]);
}

bool joint(int u, int v){
    int x = find(u), y = find(v);
    if(x == y) return false;
    if(lab[x] > lab[y]) swap(x, y);
    lab[x]+= lab[y];
    lab[y] = x;
    return true;
}

void reset_dsu(){
    memset(lab, - 1, sizeof lab);
}

void dfs(int u, int p){
    sz[u] = c[u];
    for(int v : g[u]) if(v != p){
        par[v] = u;
        h[v] = h[u] + 1;
        dfs(v, u);
        sz[u]+= sz[v];
    }
}

void update_edge(int u, int v, int w){
    if(h[u] < h[v]) swap(u, v);
    while(h[u] > h[v]){
        weight[u] = min(weight[u], w);
        u = par[u];
    }
    while(u != v){
        weight[u] = min(weight[u], w);
        weight[v] = min(weight[v], w);
        u = par[u], v = par[v];
    }
}

namespace sub123{

    void solve(){
        ll ans = 0;
        reset_dsu();

        for(int mask = 0; mask < (1 << k); mask++){
            bool ok = 1;
            for(int i = 1; i <= n; i++) g[i].clear(), lab[i] = - 1, weight[i] = 2e9, in_MST[i] = 0;

            for(int i = 0; i < k; i++) if((mask >> i) & 1){
                if(!joint(SE[i + 1].u, SE[i + 1].v)){
                    ok = false;
                    break;
                }
                if((mask >> i) & 1){
                    g[SE[i + 1].u].push_back(SE[i + 1].v);
                    g[SE[i + 1].v].push_back(SE[i + 1].u);
                }
            }

            if(!ok) continue;   

            for(int i = 1; i <= n - 1; i++){
                if(joint(MST[i].u, MST[i].v)){
                    in_MST[i] = 1;
                    g[MST[i].u].push_back(MST[i].v);
                    g[MST[i].v].push_back(MST[i].u);
                }
            }   

            dfs(1, - 1);
            for(int i = 1; i <= n; i++) if(!in_MST[i]){
                update_edge(MST[i].u, MST[i].v, MST[i].w);
            }

            ll sum = 0;
            for(int i = 0; i < k; i++) if((mask >> i) & 1){
                int u = SE[i + 1].u, v = SE[i + 1].v;
                if(h[u] > h[v]) swap(u, v);
                sum+= 1LL * weight[v] * sz[v];
            }
            ans = max(ans, sum);
        }   
        cout << ans;
    }   
}

namespace sub45{
    int color[MAX], cnt;

    void dfs(int u, int col){
        color[u] = col;
        for(int v : g[u]) if(color[v] == - 1){
            dfs(v, col);
        }
    }

    ll sum_c[MAX];
    ll SUM[MAX];

    void DFS(int u, int p){
        SUM[u] = sum_c[u];
        for(int v : g[u]) if(v != p){
            h[v] = h[u] + 1;
            par[v] = u;
            DFS(v, u);
            SUM[u]+= SUM[v];
        }
    }

    void solve(){
        reset_dsu();
        for(int i = 1; i <= k; i++){
            joint(SE[i].u, SE[i].v);
        }
        sort(E + 1, E + 1 + m, [&](Edges u, Edges v){
            return u.w < v.w;
        });
        for(int i = 1; i <= m; i++) if(joint(E[i].u, E[i].v)){
            g[E[i].u].push_back(E[i].v);
            g[E[i].v].push_back(E[i].u);
            in_MST[i] = 1;
        }

        reset_dsu();

        vector <Edges> extra;
        for(int i = 1; i <= m; i++) if(in_MST[i]){
            joint(E[i].u, E[i].v);
        }
        for(int i = 1; i <= m; i++) if(!in_MST[i]){
            if(joint(E[i].u, E[i].v)){
                extra.push_back(E[i]);
            }
        }

        memset(color, - 1, sizeof color);
        for(int i = 1; i <= n; i++) if(color[i] == - 1){
            cnt++;
            dfs(i, cnt);
        }

        for(int i = 1; i <= k; i++) SE[i].u = color[SE[i].u], SE[i].v = color[SE[i].v];
        for(auto &x : extra) x.u = color[x.u], x.v = color[x.v]; 
        for(int i = 1; i <= n; i++) sum_c[color[i]]+= c[i]; 

        ll ans = 0;
        reset_dsu();

        for(int mask = 0; mask < (1 << k); mask++){
            for(int i = 1; i <= cnt; i++) g[i].clear(), lab[i] = - 1, weight[i] = 2e9;
            bool ok = 1;
            for(int i = 0; i < k; i++) if((mask >> i) & 1){
                if(!joint(SE[i + 1].u, SE[i + 1].v)){
                    ok = 0;
                    break;
                }
                if((mask >> i) & 1){
                    g[SE[i + 1].u].push_back(SE[i + 1].v);
                    g[SE[i + 1].v].push_back(SE[i + 1].u);
                }
            }
            if(!ok) continue;   

            for(auto x : extra){
                if(joint(x.u, x.v)){
                    g[x.u].push_back(x.v);
                    g[x.v].push_back(x.u);
                }
            }

            DFS(1, - 1);

            for(auto x : extra){
                update_edge(x.u, x.v, x.w);
            }

            ll sum = 0;
            for(int i = 0; i < k; i++) if((mask >> i) & 1){
                int u = SE[i + 1].u, v = SE[i + 1].v;
                if(h[u] > h[v]) swap(u, v);
                sum+= 1LL * weight[v] * SUM[v];
            }
            ans = max(ans, sum);
        }
        cout << ans;
    }   
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("kieuoanh.inp", "r", stdin);
    // freopen("kieuoanh.out", "w", stdout);

    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
        int u, v, w; cin >> u >> v >> w;
        edges.push_back({w, u, v});
        E[i] = {u, v, w};
    }
    for(int i = 1; i <= k; i++) cin >> SE[i].u >> SE[i].v;
    for(int i = 1; i <= n; i++) cin >> c[i];

    reset_dsu();
    sort(edges.begin(), edges.end());

    int cnt = 0;
    for(array <int, 3> it : edges){
        int u = it[1], v = it[2], w = it[0];
        if(joint(u, v)){
            MST[++ cnt] = {u, v, w};
        }
    }   
        
    /// thay vì ta duyệt lại từng cạnh để check thì có nhận xét
    /*
        ta nén cây lại

        xét k cạnh đặc biệt 

        MST 1 gôm : k cạnh đặc biệt + cạnh mặc định
        MST 2 gồm : cạnh mặc định
        từ đó ta có những cạnh có khả năng cạnh tranh 

        biến đồ thị về các thành phần liên thông
        giờ ta chỉ cần duyệt mask để tìm cạnh kết nối chúng lại

        ta không cần kết nối một số cạnh kh cần thiết vì khi đã xét đủ k cạnh 
        thì ta đã có những cạnh có sẵn trong mst
    */  

    // if(max(n, m) <= 5000) return sub123::solve(), 0;
    return sub45::solve(), 0;   
    
    return 0;
}

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