oj.uz

Submission #625158

# Submission time Handle Problem Language Result Execution time Memory
625158 2022-08-09T13:55:48 Z abcvuitunggio Toll (APIO13_toll) C++17
100 / 100
 1647 ms 27012 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
struct edge{
    int u,v,w;
}e[300001],r[21];
const int inf=1e9;
int n,m,k,p[100001],l[100001],sz[100001],pre[100001],ch[300001],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 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 1 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 4 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 1 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 4 ms 2900 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 212 ms 24840 KB Output is correct
8 Correct 190 ms 26932 KB Output is correct
9 Correct 181 ms 27012 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 1 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 4 ms 2900 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 212 ms 24840 KB Output is correct
8 Correct 190 ms 26932 KB Output is correct
9 Correct 181 ms 27012 KB Output is correct
10 Correct 1328 ms 26956 KB Output is correct
11 Correct 1647 ms 26960 KB Output is correct
12 Correct 1624 ms 26940 KB Output is correct