Submission #1236672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236672		_user	Toll (APIO13_toll)	C++20	100 / 100	1140 ms	67848 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 5e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = LLONG_MAX/5;
#define bit(x,y) ((x >> y) & 1)
typedef struct
{
    ll u,v,w;
}burh;
ll cmp(burh x,burh y)
{
    return x.w < y.w;
}
burh p[N];
burh kp[N];
bool seen[N];
ll par[N],w[N],mst[N],np[N],nw[1005],limit[1005],sw[1005],parr[1005];
burh sus[1005];
vector<pair<ll,ll>> a[N];
vector<ll> b[N];
vector<ll> g[N];
ll n,m,n2,m2,k;
ll h[N];
void build(ll x, ll px)
{
    sw[x] = nw[x];
    for(auto y : g[x])
    {
        if(y == px) continue;
        parr[y] = x;
        h[y] = h[x] + 1;
        build(y,x);
        sw[x] += sw[y];
    }
}
void setlimit(ll x, ll y, ll z)
{
    if(h[x] < h[y]) swap(x,y);
    while(h[x] > h[y])
    {
        limit[x] = min(limit[x],z);
        x = parr[x];
    }
    while(x != y)
    {
        limit[x] = min(limit[x],z);
        limit[y] = min(limit[y],z);
        x = parr[x];
        y = parr[y];
    }
}
ll fp(ll x)
{
    if(par[x] == 0) return x;
    else
    {
        par[x] = fp(par[x]);
        return par[x];
    }
}
void hop(ll x, ll y)
{
    ll px = fp(x);
    ll py = fp(y);
    if(px == py) return;
    par[px] = py;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    ll i,j;
    for(i = 1;i <= m;i++)
    {
        cin >> p[i].u >> p[i].v >> p[i].w;
        a[p[i].u].push_back({p[i].v,i});
        a[p[i].v].push_back({p[i].u,i});
    }
    for(i = 1;i <= k;i++)
    {
        cin >> kp[i].u >> kp[i].v;
        b[kp[i].u].push_back(kp[i].v);
        b[kp[i].v].push_back(kp[i].u);
    }
    for(i = 1;i <= n;i++) cin >> w[i];
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>> pq;
    pq.push({0,{1,0}});
    while(!pq.empty())
    {
        ll x = pq.top().second.first;
        ll ip = pq.top().second.second;
        pq.pop();
        if(seen[x] == 1) continue;
        seen[x] = 1;
        mst[ip] = 1;
        for(auto tmp : a[x])
        {
            ll y = tmp.first;
            ll id = tmp.second;
            ll dis = p[id].w;
            if(seen[y] == 1) continue;
            pq.push({dis,{y,id}});
        }
    }
    for(i = 1;i <= n;i++) seen[i] = 0;
    pq.push({0,{1,0}});
    while(!pq.empty())
    {
        ll x = pq.top().second.first;
        ll ip = pq.top().second.second;
        pq.pop();
        if(seen[x] == 1) continue;
        seen[x] = 1;
        mst[ip]++;
        for(auto tmp : a[x])
        {
            ll y = tmp.first;
            ll id = tmp.second;
            ll dis = p[id].w;
            if(seen[y] == 1) continue;
            pq.push({dis,{y,id}});
        }
        for(auto y : b[x])
        {
            if(seen[y] == 1) continue;
            pq.push({0,{y,0}});
        }
    }
    for(i = 1;i <= m;i++)
    {
        if(mst[i] == 2)
        {
            hop(p[i].u,p[i].v);
        }
    }
    for(i = 1;i <= n;i++)
    {
        if(np[fp(i)] == 0)
        {
            np[fp(i)] = ++n2;
        }
        np[i] = np[fp(i)];
        nw[np[i]] += w[i];
    }
    for(i = 1;i <= n;i++) par[i] = 0;
    for(i = 1;i <= k;i++)
    {
        kp[i].u = np[kp[i].u];
        kp[i].v = np[kp[i].v];
    }
    for(i = 1;i <= m;i++)
    {
        if(mst[i] == 1)
        {
            if(np[p[i].u] != np[p[i].v])
            {
                sus[++m2] = {np[p[i].u],np[p[i].v],p[i].w};
            }
        }
    }
    sort(sus + 1,sus + 1 + m2,cmp);
    ll tans = 0;
    for(i = 0;i < (1 << k);i++)
    {
        for(j = 1;j <= n2;j++)
        {
            par[j] = 0;
            g[j].clear();
        }
        ll flag = 0;
        for(j = 1;j <= k;j++)
        {
            if(bit(i,j - 1))
            {
                if(fp(kp[j].u) == fp(kp[j].v))
                {
                    flag = 1;
                    break;
                }else
                {
                    hop(kp[j].u,kp[j].v);
                    g[kp[j].u].push_back(kp[j].v);
                    g[kp[j].v].push_back(kp[j].u);
                }
            }
        }
        if(flag == 1) continue;
        for(j = 1;j <= m2;j++)
        {
            if(fp(sus[j].u) != fp(sus[j].v))
            {
                hop(sus[j].u,sus[j].v);
                g[sus[j].u].push_back(sus[j].v);
                g[sus[j].v].push_back(sus[j].u);
            }
        }
        h[1] = 1;
        build(1,0);
        for(j = 1;j <= n2;j++)
        {
            limit[j] = inf;
        }
        for(j = 1;j <= m2;j++)
        {
            setlimit(sus[j].u,sus[j].v,sus[j].w);
        }
        ll ans = 0;
        for(j = 1;j <= k;j++)
        {
            if(bit(i,j - 1))
            {
                if(h[kp[j].u] < h[kp[j].v]) swap(kp[j].u,kp[j].v);
                ll x = kp[j].u;
                ans += limit[x] * sw[x];
            }
        }
        tans = max(tans,ans);
    }
    cout << tans;
}

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