oj.uz

Submission #757745

# Submission time Handle Problem Language Result Execution time Memory
757745 2023-06-13T17:31:54 Z nonono Toll (APIO13_toll) C++14
56 / 100
 2500 ms 24348 KB 
#include "bits/stdc++.h"
using namespace std;

struct DSU {
    
    vector<int> lab;
    
    void init(int n){
        lab.resize(n + 5);
        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;
    }
} dsu; 

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];

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){
    
    dsu.init(n);
    for(int i = 1; i <= n; i ++){
        par[i] = 0;
        h[i] = 0;
        
        adj[i].clear();
        cost[i] = Linf;
    }
    
    for(int i = 1; i <= k; i ++){
        if(mask >> (i - 1) & 1){
            int u = edge[i + m][1];
            int v = edge[i + m][2];
            
            if(dsu.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 = 1; i <= m; i ++){
        int w = edge[i][0];
        int u = edge[i][1];
        int v = edge[i][2];
        
        if(dsu.unite(u, v)){
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        } else {
            oth.push_back({u, v, w});
        }
    }
    
    dfs(1, 1);
    
    for(auto [u, v, w] : oth){
        update(u, v, w);
    }
    
    return Dfs(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);
    
    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:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto [v, w] : adj[u]){
      |              ^
toll.cpp: In function 'long long int Dfs(int, int)':
toll.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     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 [u, v, w] : 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 2704 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 2704 KB Output is correct
3 Correct 4 ms 2708 KB Output is correct
4 Correct 4 ms 2644 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 2704 KB Output is correct
3 Correct 4 ms 2708 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 435 ms 2900 KB Output is correct
6 Correct 195 ms 2900 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 2704 KB Output is correct
3 Correct 4 ms 2708 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 435 ms 2900 KB Output is correct
6 Correct 195 ms 2900 KB Output is correct
7 Execution timed out 2539 ms 24348 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 2704 KB Output is correct
3 Correct 4 ms 2708 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 435 ms 2900 KB Output is correct
6 Correct 195 ms 2900 KB Output is correct
7 Execution timed out 2539 ms 24348 KB Time limit exceeded
8 Halted 0 ms 0 KB -