oj.uz

Submission #758175

# Submission time Handle Problem Language Result Execution time Memory
758175 2023-06-14T08:42:19 Z nonono Toll (APIO13_toll) C++14
100 / 100
 1971 ms 23560 KB 
#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

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.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 2 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 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct

Subtask #4
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 2 ms 2644 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 173 ms 16908 KB Output is correct
8 Correct 187 ms 23388 KB Output is correct
9 Correct 189 ms 23404 KB Output is correct

Subtask #5
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 2 ms 2644 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 173 ms 16908 KB Output is correct
8 Correct 187 ms 23388 KB Output is correct
9 Correct 189 ms 23404 KB Output is correct
10 Correct 1404 ms 23500 KB Output is correct
11 Correct 1961 ms 23524 KB Output is correct
12 Correct 1971 ms 23560 KB Output is correct