Submission #1155908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155908		vicvic	Toll (APIO13_toll)	C++20	100 / 100	952 ms	14640 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <functional>
#include <unordered_map>
#define int long long
using namespace std;
const int NMAX=1e5, MMAX=3e5, KMAX=20;
int ord[MMAX+5], u[MMAX+5], v[MMAX+5], w[MMAX+5], n, m, k, x[MMAX+5], y[MMAX+5], people[NMAX+5], used[MMAX+5], label[MMAX+5], total[MMAX+5], dp[MMAX+5], dp2[MMAX+5];
class DSU
{
public:
    int sz;
    vector <int> t;
    DSU (int n=0): sz (n), t (n+1, -1) {};
    void reset (int n)
    {
        sz=n;
        t.resize (n+1);
        for (int i=0;i<=n;i++)
        {
            t[i]=-1;
        }
    }
    int get (int nod) {return t[nod]<0?nod:t[nod]=get (t[nod]);}
    bool same (int nod, int nod1) {return get (nod)==get (nod1);}
    void join (int x, int y)
    {
        x=get (x), y=get (y);
        if (x==y)
            return;
        t[y]=x;
    }
};
int32_t main ()
{
    ios :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> m >> k;
    for (int i=0;i<m;i++)
    {
        cin >> u[i] >> v[i] >> w[i];
        ord[i]=i;
    }
    for (int i=0;i<k;i++)
    {
        cin >> x[i] >> y[i];
    }
    for (int i=1;i<=n;i++)
    {
        cin >> people[i];
    }
    sort (ord, ord+m, [] (int a, int b) {return w[a]<w[b];});
    DSU dsu (n);
    for (int i=0;i<k;i++)
    {
        if (!dsu.same (x[i], y[i])) dsu.join (x[i], y[i]);
    }
    for (int i=0;i<m;i++)
    {
        if (!dsu.same (u[ord[i]], v[ord[i]])) dsu.join (u[ord[i]], v[ord[i]]), used[ord[i]]=1;
    }
    dsu.reset (n);
    for (int i=0;i<m;i++)
    {
        if (used[ord[i]]) dsu.join (u[ord[i]], v[ord[i]]);
    }
    unordered_map <int, int> component;
    int c=0;
    for (int i=1;i<=n;i++)
    {
        int current=dsu.get (i);
        if (component.find(current)==component.end()) component[current]=++c;
        label[i]=component[current];
        total[label[i]]+=people[i];
    }
    for (int i=0;i<m;i++)
    {
        u[ord[i]]=label[u[ord[i]]];
        v[ord[i]]=label[v[ord[i]]];
    }
    for (int i=0;i<k;i++)
    {
        x[i]=label[x[i]];
        y[i]=label[y[i]];
    }
    vector <int> undid;
    dsu.reset (c);
    for (int i=0;i<m;i++)
    {
        if (!dsu.same (u[ord[i]], v[ord[i]])) dsu.join (u[ord[i]], v[ord[i]]), undid.push_back (ord[i]);
    }
    vector <vector <int>> vec (c+1);
    vector <int> parent (c+1), ub (c+1), depth (c+1), added ((int) undid.size());
    function<void(int, int)> dfs = [&] (int nod, int p=0)
    {
        parent[nod]=p;
        dp[nod]=total[nod];
        for (auto adj : vec[nod])
        {
            if (adj==p)
                continue;
            depth[adj]=depth[nod]+1;
            dfs (adj, nod);
            dp[nod]+=dp[adj];
        }
    };
    int mx=-1;
    for (int msk=0;msk<(1 << k);msk++)
    {
        for (int i=0;i<=c;i++)
        {
            vec[i].clear ();
            dp2[i]=1e9;
            depth[i]=0;
        }
        dsu.reset (c);
        int cycle=0;
        for (int i=0;i<k;i++)
        {
            if ((msk >> i) & 1)
            {
                if (dsu.same (x[i], y[i]))
                {
                    cycle=1;
                    break;
                }
                dsu.join (x[i], y[i]);
                vec[x[i]].push_back (y[i]);
                vec[y[i]].push_back (x[i]);
            }
        }
        if (cycle)
            continue;
        for (int i=0;i<undid.size();i++)
        {
            int crtord=undid[i];
            used[i]=!dsu.same (u[crtord], v[crtord]);
            if (!dsu.same (u[crtord], v[crtord]))
            {
                dsu.join (u[crtord], v[crtord]);
                vec[u[crtord]].push_back (v[crtord]);
                vec[v[crtord]].push_back (u[crtord]);
            }
        }
        dfs (1ll, 0);
        for (int i=0;i<undid.size();i++)
        {
            if (!used[i])
            {
                int crtord=undid[i];
                int x=u[crtord], y=v[crtord], val=w[crtord];
                if (depth[x]<depth[y])
                    swap (x, y);
                for (;depth[x]>depth[y];x=parent[x]) dp2[x]=min (dp2[x], val);
                for (;x!=y;x=parent [x], y=parent[y]) dp2[x]=min (dp2[x], val), dp2[y]=min (dp2[y], val);
            }
        }
        int cur=0;
        for (int i=0;i<k;i++)
        {
            if (msk & (1 << i))
            {
                int n=x[i], n1=y[i];
                if (n==parent[n1])
                {
                    swap (n, n1);
                }
                cur+=dp[n]*dp2[n];
            }
        }
        mx=max (mx, cur);
    }
    cout << mx;
    return 0;
}

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