oj.uz

Submission #233821

# Submission time Handle Problem Language Result Execution time Memory
233821 2020-05-21T20:39:17 Z crackersamdjam Toll (APIO13_toll) C++14
16 / 100
 2500 ms 2816 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define e edges[i]
using namespace std;
typedef long long ll;
constexpr int MM = 1e5+1, NN = 22;

int n, m, k, par[MM], compid[MM];
vector<int> adj[MM];

int find(int x){
    while(x != par[x])
        x = par[x], par[x] = par[par[x]];
    return x;
}

void reset(){
    for(int i = 0; i <= n; i++)
        par[i] = i;
}

struct edge{
    int a, b, c;
    bool operator<(const edge o) const{
        return c < o.c;
    }
} edges[MM], toll[NN];
vector<int> use, maybe, no;
int pre[NN], dep[NN], dp[NN];
ll compsz[NN], ans;

void dfs(int cur){
    for(int u: adj[cur]){
        if(u != pre[cur]){
            pre[u] = cur;
            dep[u] = dep[cur]+1;
            dfs(u);
            compsz[cur] += compsz[u]; //subtree sz
        }
    }
}

void go(int mask){
    for(int i = 0; i < 25; i++){
        par[i] = i;
        dp[i] = 1e6;
    }
    
    for(int i = 0; i < k; i++){
        if(mask&(1<<i)){
            int a = find(compid[toll[i].a]), b = find(compid[toll[i].b]);
            if(a == b)
                return; //cycle
            par[a] = b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
    }
    
    //add so that graph is connected
    no.clear();
    for(int i: maybe){
        int a = find(e.a), b = find(e.b);
        if(a != b)
            par[a] = b;
        else
            no.push_back(i);
    }
    
    pre[compid[1]] = -1;
    dfs(compid[1]);
    
    //update with unused edges
    for(int i: no){
        //lift
        int a = e.a, b = e.b;
        if(dep[a] < dep[b])
            swap(a, b);
        while(dep[a] > dep[b]){
            dp[a] = min(dp[a], e.c);
            a = pre[a];
        }
        while(a != b){
            dp[a] = min(dp[a], e.c);
            a = pre[a];
            dp[b] = min(dp[b], e.c);
            b = pre[b];
        }
    }
    
    ll sum = 0;
    
    for(int i = 0; i < k; i++){
        if(mask&(1<<i)){
            int a = compid[toll[i].a], b = compid[toll[i].b]; //don't do find() bc not merging
            a = (dep[a] > dep[b] ? a : b);
            sum += dp[a]*compsz[a];
        }
    }
    ans = max(ans, sum);
}

int main(){
    use.resize(n);
    maybe.resize(22);
    no.reserve(22);
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    freopen("in.txt", "r", stdin);
    cin>>n>>m>>k;
    for(int i = 0,a,b,c; i < m; i++){
        cin>>a>>b>>c;
        edges[i] = {a, b, c};
    }
    reset();
    for(int i = 0,a,b; i < k; i++){
        cin>>a>>b;
        toll[i] = {a, b};
        par[find(a)] = find(b);
    }
    sort(edges, edges+m);
    
    for(int i = 0; i < m; i++){
        int a = find(e.a), b = find(e.b);
        if(a != b){
            par[a] = b;
            use.push_back(i);
//            cout<<"use "<<e.a<<' '<<e.b<<' '<<e.c<<endl;
        }
    }
    
    //second time without Ks
    reset();
    for(int i: use){
        int a = find(e.a), b = find(e.b);
        par[a] = b;
    }
    
    //compress graph
    int t = 0;
    for(int i = 1; i <= n; i++){
        if(find(i) == i)
            compid[i] = t++;
    }
    
    for(int i = 1; i <= n; i++)
        compid[i] = compid[find(i)];
    
    for(int i = 1,szz; i <= n; i++){
        cin>>szz;
        compsz[compid[i]] += szz;
    }
    
    // add maybe edges
    for(int i = 0; i < m; i++){
        int a = find(e.a), b = find(e.b);
        if(a != b){
            par[a] = b;
            
            a = compid[a], b = compid[b];
            adj[a].push_back(b);
            adj[b].push_back(a);
            
            e.a = a, e.b = b;
            maybe.push_back(i);
        }
    }
    
    for(int i = 0; i < (1<<k); i++)
        go(i);
    
    cout<<ans<<'\n';
    
    return 0;
}

Compilation message

toll.cpp: In function 'void go(int)':
toll.cpp:46:15: warning: iteration 22 invokes undefined behavior [-Waggressive-loop-optimizations]
         dp[i] = 1e6;
         ~~~~~~^~~~~
toll.cpp:44:22: note: within this loop
     for(int i = 0; i < 25; i++){
                    ~~^~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Execution timed out 2574 ms 2816 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Execution timed out 2574 ms 2816 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Execution timed out 2574 ms 2816 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Execution timed out 2574 ms 2816 KB Time limit exceeded
4 Halted 0 ms 0 KB -