oj.uz

Submission #758170

# Submission time Handle Problem Language Result Execution time Memory
758170 2023-06-14T08:35:51 Z nonono Toll (APIO13_toll) C++14
56 / 100
 2500 ms 16348 KB 
#include "bits/stdc++.h"
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>> oth;

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;
            }
        }
    }
    
    for(int i = 1; i <= m; i ++){
        int w = edge[i][0];
        int u = edge[i][1];
        int v = edge[i][2];
        
        u = type[u];
        v = type[v];
        
        if(unite(u, v)){
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
    }
    
    dfs(type[1], -1);
    
    for(auto [w, u, v] : 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 {
                oth.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

toll.cpp: In function 'void dfs(int, int)':
toll.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     for(auto [v, w] : adj[u]){
      |              ^
toll.cpp: In function 'long long int Dfs(int, int)':
toll.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto [v, w] : adj[u]){
      |              ^
toll.cpp: In function 'long long int calc(int)':
toll.cpp:131:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  131 |     for(auto [w, u, v] : oth){
      |              ^

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 3 ms 2696 KB Output is correct
5 Correct 37 ms 2844 KB Output is correct
6 Correct 25 ms 2844 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 3 ms 2696 KB Output is correct
5 Correct 37 ms 2844 KB Output is correct
6 Correct 25 ms 2844 KB Output is correct
7 Execution timed out 2537 ms 16348 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 3 ms 2696 KB Output is correct
5 Correct 37 ms 2844 KB Output is correct
6 Correct 25 ms 2844 KB Output is correct
7 Execution timed out 2537 ms 16348 KB Time limit exceeded
8 Halted 0 ms 0 KB -