Submission #889270

#	Time	Username	Problem	Language	Result	Execution time	Memory
889270		fdnfksd	Toll (APIO13_toll)	C++14	100 / 100	1265 ms	45004 KiB

toll

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll P[maxn];
vector<pli>g[maxn];
ll ww[maxn];
ll nxt[maxn],h[maxn],sz[maxn];
void dfs(ll u,ll p)
{
    P[u]=p;
    //cout << u << '\n';
    for(auto vv:g[u])
    {
        int v=vv.fi;
        int w=ww[vv.se];

        if(v!=p)
        {
            nxt[v]=vv.se;
            //cout << u << ' '<<v<<' '<<vv.se<<'\n';
            h[v]=h[u]+1;
            dfs(v,u);
        }
    }
}
ll ss=0;
ll val[maxn];
void DFS(ll u,ll p)
{
    sz[u]=val[u];
    for(auto vv:g[u])
    {
        int v=vv.fi;
        int w=ww[vv.se];

        if(v!=p)
        {
            DFS(v,u);
            sz[u]+=sz[v];
            ss+=sz[v]*w;
        }
    }
}
void update(ll u,ll v,ll w)
{
    while(u!=v)
    {
        if(h[u]>h[v])
        {
            ww[nxt[u]]=min(ww[nxt[u]],w);
            u=P[u];
        }
        else
        {
            ww[nxt[v]]=min(ww[nxt[v]],w);
            v=P[v];
        }
    }
}
ll node=0;
ll lab[maxn];
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
ll sum[maxn];
bool  unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(u==v) return false;
    if(lab[u]>lab[v]) swap(u,v);
    lab[u]+=lab[v];
    lab[v]=u;
    sum[u]+=sum[v];
    return true;
}
ll k;
struct edge
{
    ll u,v,w;
    bool operator<(const edge&o)
    {
        return w<o.w;
    }
}e[maxn],d[maxn];
vector<edge>t2,t3;
ll id[maxn],ans=0;
void cal(ll mask)
{
    for(int i=1;i<=node;i++) lab[i]=-1,g[i].clear();
    ww[0]=0;
    for(int i=1;i<=k;i++) ww[i]=inf;
    for(int i=1;i<=k;i++)
    {
        if(mask>>(i-1)&1)
        {
            if(unite(d[i].u,d[i].v))
            {
                g[d[i].u].pb({d[i].v,i});
                g[d[i].v].pb({d[i].u,i});
                //cout << i << '\n';
            }
        }
    }
    vector<edge>djt;
    for(auto zz:t3)
    {
        if(unite(zz.u,zz.v))
        {
            g[zz.u].pb({zz.v,0});
            g[zz.v].pb({zz.u,0});
        }
        else
        {
            djt.pb(zz);
        }
    }
    dfs(id[1],0);
    for(auto zz:djt)
    {
        update(zz.u,zz.v,zz.w);
    }
    ss=0;
    DFS(id[1],0);
    ans=max(ans,ss);
}
ll n,m,p[maxn],vv[maxn];
bool in[maxn];
void solve()
{
    cin >> n >> m >> k;
    for(int i=1;i<=m;i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    for(int i=1;i<=k;i++)
    {
        cin >> d[i].u >> d[i].v ;
        d[i].w=inf;
    }
    for(int i=1;i<=n;i++) cin >> p[i];
    sort(e+1,e+m+1);

    for(int i=1;i<=n;i++) lab[i]=-1,sum[i]=p[i];
    for(int i=1;i<=m;i++)
    {
        if(unite(e[i].u,e[i].v)) in[i]=true;
    }
    for(int i=1;i<=n;i++) lab[i]=-1,sum[i]=p[i];
    for(int i=1;i<=k;i++)
    {
        unite(d[i].u,d[i].v);
    }
    for(int i=1;i<=m;i++)
    {
        if(unite(e[i].u,e[i].v)) t2.pb(e[i]);
        else if(in[i]==true) t3.pb(e[i]);
    }
    for(int i=1;i<=n;i++) lab[i]=-1,sum[i]=p[i];
    for(auto zz:t2)
    {
        unite(zz.u,zz.v);
    }
    node=0;
    for(int i=1;i<=n;i++)
    {
        if(findset(i)==i)
        {
            vv[i]=++node;
            val[node]=sum[i];
        }
    }
    for(int i=1;i<=n;i++)
    {
        id[i]=vv[findset(i)];
    }
    for(int i=1;i<=k;i++)
    {
        d[i].u=id[d[i].u];
        d[i].v=id[d[i].v];
    }
    for(auto &zz:t3)
    {
        zz.u=id[zz.u];
        zz.v=id[zz.v];
    }
    for(int mask=0;mask<(1<<k);mask++)
    {
        cal(mask);
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen("c.INP","r",stdin);
    //freopen("c.OUT","w",stdout);
    solve();
}

Compilation message (stderr)

toll.cpp: In function 'void dfs(ll, ll)':
toll.cpp:24:13: warning: unused variable 'w' [-Wunused-variable]
   24 |         int w=ww[vv.se];
      |             ^

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22