oj.uz

Submission #889270

# Submission time Handle Problem Language Result Execution time Memory
889270 2023-12-19T09:27:27 Z fdnfksd Toll (APIO13_toll) C++14
100 / 100
 1265 ms 45004 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 5 ms 31064 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 5 ms 31064 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 5 ms 31064 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 118 ms 44456 KB Output is correct
8 Correct 131 ms 44740 KB Output is correct
9 Correct 123 ms 44640 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 5 ms 31064 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 118 ms 44456 KB Output is correct
8 Correct 131 ms 44740 KB Output is correct
9 Correct 123 ms 44640 KB Output is correct
10 Correct 894 ms 44496 KB Output is correct
11 Correct 1265 ms 45004 KB Output is correct
12 Correct 1245 ms 44884 KB Output is correct