Submission #758175

#	Time	Username	Problem	Language	Result	Execution time	Memory
758175		nonono	Toll (APIO13_toll)	C++14	100 / 100	1971 ms	23560 KiB

toll

#include "bits/stdc++.h"
#define int long long
using namespace std;

const int Linf = 1e9 + 20;
const int mxN = 1e5 + 20;
const int mxM = 3e5 + 20;

int n, m, k;
array<int, 3> edge[mxM + 10];
int cnt[mxN];

vector<vector<pair<int, int>>> adj(mxN);
int par[mxN], h[mxN], cost[mxN];
int siz[mxN];

int Used[mxM], _Used[mxM], type[mxN];
int lab[mxN];
vector<int> T;
vector<array<int, 3>> e;

void reset(){
    for(int i = 1; i <= n; i ++) lab[i] = -1;
}

int get_root(int u){
    return lab[u] < 0 ? u : lab[u] = get_root(lab[u]);
}

bool unite(int u, int v){
    u = get_root(u); 
    v = get_root(v);
        
    if(u == v) return false;
    if(lab[u] > lab[v]) swap(u, v);
        
    lab[u] += lab[v];
    lab[v] = u;
        
    return true;
}

void dfs(int u, int p){
    par[u] = p;
    for(auto [v, w] : adj[u]){
        if(v == p) continue ;
        
        h[v] = h[u] + 1;
        dfs(v, u);
    }
}

long long Dfs(int u, int p){
    long long tmp = 0;
    siz[u] = cnt[u];
    
    for(auto [v, w] : adj[u]){
        if(v == p) continue ;
        
        tmp += Dfs(v, u);
        
        if(!w) tmp += 1LL * siz[v] * cost[v];
        siz[u] += siz[v];
    }
    
    return tmp;
}

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

long long calc(int mask){
    
    for(auto x : T){
        par[x] = 0;
        h[x] = 0;
        
        adj[x].clear();
        cost[x] = Linf;
        
        lab[x] = -1;
    }
    
    for(int i = 1; i <= k; i ++){
        if(mask >> (i - 1) & 1){
            int u = edge[i + m][1];
            int v = edge[i + m][2];
            
            u = type[u];
            v = type[v];
            
            if(unite(u, v)){
                adj[u].push_back({v, 0});
                adj[v].push_back({u, 0});
            } else {
                return -1;
            }
        }
    }
    
    vector<array<int, 3>> oth;
    
    for(int i = 0; i < e.size(); i ++){
        int w = e[i][0];
        int u = e[i][1];
        int v = e[i][2];
        
        u = type[u];
        v = type[v];
        
        if(unite(u, v)){
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        } else {
            oth.push_back({u, v, w});
        }
    }
    
    dfs(type[1], -1);
    
    for(auto [u, v, w] : oth){
        u = type[u];
        v = type[v];
        
        update(u, v, w);
    }
    
    return Dfs(type[1], -1);
}

signed main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> k;
    
    for(int i = 1; i <= m; i ++){
        int u, v, w;
        cin >> u >> v >> w;
        edge[i] = {w, u, v};
    }
    
    for(int i = 1; i <= k; i ++){
        int u, v;
        cin >> u >> v;
        
        edge[m + i] = {0, u, v};
    }
    
    for(int i = 1; i <= n; i ++){
        cin >> cnt[i];
    }
    
    sort(edge + 1, edge + 1 + m);
    
    reset();
    for(int i = 1; i <= m; i ++) Used[i] = unite(edge[i][1], edge[i][2]);
    
    reset();
    for(int i = 1; i <= k; i ++) unite(edge[i + m][1], edge[i + m][2]);
    for(int i = 1; i <= m; i ++) _Used[i] = unite(edge[i][1], edge[i][2]);
    
    reset();
    for(int i = 1; i <= m; i ++){
        if(Used[i]){
            if(_Used[i]){
                unite(edge[i][1], edge[i][2]);    
            } else {
                e.push_back(edge[i]);
            }
        }
    }
    
    for(int i = 1; i <= n; i ++){
        int x = get_root(i);
        type[i] = x;
        
        if(x == i){
            T.push_back(i);
        } else {
            cnt[x] += cnt[i];
        }
    }
    
    long long Res = 0;
    for(int mask = 0; mask < (1 << k); mask ++){
        Res = max(Res, calc(mask));
    }
    
    cout << Res << "\n";
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'void dfs(long long int, long long int)':
toll.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for(auto [v, w] : adj[u]){
      |              ^
toll.cpp: In function 'long long int Dfs(long long int, long long int)':
toll.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for(auto [v, w] : adj[u]){
      |              ^
toll.cpp: In function 'long long int calc(long long int)':
toll.cpp:118:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i = 0; i < e.size(); i ++){
      |                    ~~^~~~~~~~~~
toll.cpp:136:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  136 |     for(auto [u, v, w] : oth){
      |              ^

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