oj.uz

Submission #354293

# Submission time Handle Problem Language Result Execution time Memory
354293 2021-01-21T16:47:15 Z denkendoemeer Toll (APIO13_toll) C++14
100 / 100
 2205 ms 14024 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int>g[100005],aux;
array<int,3>ed[300005];
array<int,2>edk[25];
ll sum[25],ans;
int d[25],t[25],w[25],comp[100005],u;
template<int sz>
struct dsu
{
    int t[sz];
    int findt(int nod)
    {
        if (nod==t[nod])
            return nod;
        return t[nod]=findt(t[nod]);
    }
    bool onion(int x,int y)
    {
        x=findt(x);
        y=findt(y);
        t[y]=x;
        if (x==y)
            return 0;
        return 1;
    }
};
dsu<100005>d1,d2,d3;
dsu<25>d4,d5;
void dfs(int nod,int ta)
{
    t[nod]=ta;
    if (ta==-1)
        d[nod]=0;
    else
        d[nod]=d[ta]+1;
    for(auto it:g[nod])
        if (it!=ta)
            dfs(it,nod);
}
ll dfs2(int nod,ll s)
{
    ll cnt=s*sum[nod];
    for(auto it:g[nod])
        if (it!=t[nod])
            cnt=cnt+dfs2(it,s+w[it]);
    return cnt;

}
deque<array<int,3>>dq;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m,k,x;
    scanf("%d%d%d",&n,&m,&k);
    int i;
    for(i=0;i<m;i++)
        scanf("%d%d%d",&ed[i][1],&ed[i][2],&ed[i][0]),--ed[i][1],--ed[i][2];
    sort(ed,ed+m);
    for(i=0;i<n;i++)
        d1.t[i]=i,d2.t[i]=i,d3.t[i]=i;
    for(i=0;i<k;i++){
        scanf("%d%d",&edk[i][0],&edk[i][1]);
        --edk[i][0];
        --edk[i][1];
        d1.onion(edk[i][0],edk[i][1]);
    }
    for(i=0;i<m;i++){
        if (d2.onion(ed[i][1],ed[i][2])==0)
            continue;
        if (d1.onion(ed[i][1],ed[i][2]))
            d3.onion(ed[i][1],ed[i][2]);
        else
            aux.push_back(i);
    }
    for(i=0;i<n;i++)
        if (d3.findt(i)==i)
            comp[i]=u++;
    for(i=0;i<n;i++){
        scanf("%d",&x);
        sum[comp[d3.findt(i)]]+=x;
    }
    for(auto it:aux){
        ed[it][1]=comp[d3.findt(ed[it][1])];
        ed[it][2]=comp[d3.findt(ed[it][2])];
    }
    for(i=0;i<k;i++){
        edk[i][0]=comp[d3.findt(edk[i][0])];
        edk[i][1]=comp[d3.findt(edk[i][1])];
    }
    int j;
    for(i=0;i<(1<<k);i++){
        for(j=0;j<u;j++)
            g[j].clear();
        for(j=0;j<u;j++)
            d4.t[j]=j,d5.t[j]=j;
        for(j=0;j<k;j++){
            if (i&(1<<j) && d4.onion(edk[j][0],edk[j][1])){
                g[edk[j][0]].push_back(edk[j][1]);
                g[edk[j][1]].push_back(edk[j][0]);
            }
        }
        dq.clear();
        for(auto it:aux){
            if (d4.onion(ed[it][1],ed[it][2])){
                g[ed[it][1]].push_back(ed[it][2]);
                g[ed[it][2]].push_back(ed[it][1]);
                dq.push_front((array<int,3>){0,ed[it][1],ed[it][2]});
            }
            else
                dq.push_back(ed[it]);
        }
        dfs(comp[d3.findt(0)],-1);
        for(auto it:dq){
            int x,y;
            x=d5.findt(it[1]);
            y=d5.findt(it[2]);
            while(x!=y){
                if (d[x]<d[y])
                    swap(x,y);
                w[x]=it[0];
                d5.onion(t[x],x);
                x=d5.findt(x);
            }
        }
        ans=max(ans,dfs2(comp[d3.findt(0)],0));
    }
    printf("%lld\n",ans);
return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     scanf("%d%d%d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
toll.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |         scanf("%d%d%d",&ed[i][1],&ed[i][2],&ed[i][0]),--ed[i][1],--ed[i][2];
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         scanf("%d%d",&edk[i][0],&edk[i][1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2728 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2728 KB Output is correct
5 Correct 5 ms 2796 KB Output is correct
6 Correct 5 ms 2796 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2728 KB Output is correct
5 Correct 5 ms 2796 KB Output is correct
6 Correct 5 ms 2796 KB Output is correct
7 Correct 215 ms 13932 KB Output is correct
8 Correct 226 ms 13804 KB Output is correct
9 Correct 229 ms 13804 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2728 KB Output is correct
5 Correct 5 ms 2796 KB Output is correct
6 Correct 5 ms 2796 KB Output is correct
7 Correct 215 ms 13932 KB Output is correct
8 Correct 226 ms 13804 KB Output is correct
9 Correct 229 ms 13804 KB Output is correct
10 Correct 1698 ms 13932 KB Output is correct
11 Correct 2205 ms 13940 KB Output is correct
12 Correct 2170 ms 14024 KB Output is correct