oj.uz

Submission #625157

# Submission time Handle Problem Language Result Execution time Memory
625157 2022-08-09T13:55:03 Z abcvuitunggio Toll (APIO13_toll) C++17
56 / 100
 32 ms 12088 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
struct edge{
    int u,v,w;
}e[100001],r[21];
const int inf=1e9;
int n,m,k,p[100001],l[100001],sz[100001],pre[100001],ch[100001],par[100001],d[100001],val[100001],res;
vector <edge> ve,v2,v3;
vector <int> ke[100001],nodes;
int f(int i){
    return (l[i]==i?i:l[i]=f(l[i]));
}
void unite(int i, int j){
    i=f(i);
    j=f(j);
    if (sz[i]>sz[j])
        swap(i,j);
    l[j]=i;
    sz[i]+=sz[j];
}
void prep(){
    for (int i:nodes){
        l[i]=pre[i];
        sz[i]=p[i];
    }
}
bool operator <(edge a, edge b){
    return a.w<b.w;
}
void dfs(int u, int parent){
    sz[u]=p[u];
    for (int v:ke[u])
        if (v!=parent){
            d[v]=d[u]+1;
            par[v]=u;
            dfs(v,u);
            sz[u]+=sz[v];
        }
}
int calc(int mask){
    prep();
    int root=f(1);
    for (int i:nodes){
        ke[i].clear();
        val[i]=inf;
    }
    for (int i=0;i<k;i++){
        r[i].w=inf;
        if ((mask>>i)&1){
            if (f(r[i].u)==f(r[i].v))
                return 0;
            unite(r[i].u,r[i].v);
            ke[r[i].u].push_back(r[i].v);
            ke[r[i].v].push_back(r[i].u);
        }
    }
    for (int i=0;i<ve.size();i++){
        if (f(ve[i].u)==f(ve[i].v)){
            ch[i]=0;
            continue;
        }
        ch[i]=1;
        unite(ve[i].u,ve[i].v);
        ke[ve[i].u].push_back(ve[i].v);
        ke[ve[i].v].push_back(ve[i].u);
    }
    d[root]=0;
    dfs(root,root);
    for (int i=0;i<ve.size();i++){
        if (ch[i])
            continue;
        int u=ve[i].u,v=ve[i].v;
        if (d[u]<d[v])
            swap(u,v);
        while (d[u]>d[v]){
            val[u]=min(val[u],ve[i].w);
            u=par[u];
        }
        while (u!=v){
            val[u]=min(val[u],ve[i].w);
            val[v]=min(val[v],ve[i].w);
            u=par[u];
            v=par[v];
        }
    }
    int res=0;
    for (int i=0;i<k;i++)
        if ((mask>>i)&1){
            int u=r[i].u,v=r[i].v;
            if (u==par[v])
                swap(u,v);
            res+=sz[u]*val[u];
        }
    return res;
}
signed main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> m >> k;
    for (int i=0;i<m;i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    for (int i=0;i<k;i++)
        cin >> r[i].u >> r[i].v;
    for (int i=1;i<=n;i++){
        cin >> p[i];
        pre[i]=i;
        nodes.push_back(i);
    }
    prep();
    sort(e,e+m);
    for (int i=0;i<m;i++){
        if (f(e[i].u)==f(e[i].v))
            continue;
        unite(e[i].u,e[i].v);
        ve.push_back(e[i]);
    }
    prep();
    for (int i=0;i<k;i++)
        unite(r[i].u,r[i].v);
    for (auto i:ve){
        if (f(i.u)==f(i.v))
            continue;
        unite(i.u,i.v);
        v2.push_back(i);
    }
    prep();
    for (auto i:v2)
        unite(i.u,i.v);
    for (auto &i:ve)
        i={f(i.u),f(i.v),i.w};
    for (auto &i:v2)
        i={f(i.u),f(i.v),i.w};
    for (int i=0;i<k;i++)
        r[i]={f(r[i].u),f(r[i].v),inf};
    nodes.clear();
    for (int i=1;i<=n;i++){
        pre[i]=f(i);
        p[i]=sz[i];
        if (i==pre[i])
            nodes.push_back(i);
    }
    prep();
    for (auto i:ve){
        if (f(i.u)==f(i.v))
            continue;
        unite(i.u,i.v);
        v3.push_back(i);
    }
    swap(ve,v3);
    for (int i=0;i<(1<<k);i++)
        res=max(res,calc(i));
    cout << res;
}

Compilation message

toll.cpp: In function 'long long int calc(long long int)':
toll.cpp:61:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i=0;i<ve.size();i++){
      |                  ~^~~~~~~~~~
toll.cpp:73:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i=0;i<ve.size();i++){
      |                  ~^~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2684 KB Output is correct
4 Correct 2 ms 2680 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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2684 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 4 ms 2952 KB Output is correct
6 Correct 4 ms 2948 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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2684 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 4 ms 2952 KB Output is correct
6 Correct 4 ms 2948 KB Output is correct
7 Runtime error 32 ms 12088 KB Execution killed with signal 11
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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2684 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 4 ms 2952 KB Output is correct
6 Correct 4 ms 2948 KB Output is correct
7 Runtime error 32 ms 12088 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -