Submission #354293

#	Time	Username	Problem	Language	Result	Execution time	Memory
354293		denkendoemeer	Toll (APIO13_toll)	C++14	100 / 100	2205 ms	14024 KiB

toll

#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 (stderr)

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 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22