Submission #1145864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145864		ALTAKEXE	Toll (APIO13_toll)	C++20	16 / 100	2595 ms	328 KiB

toll

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pii pair<int, int>
#define pb push_back
#define eb emplace_back
#define inf INT_MAX
#define all(x) x.begin(), x.end()
const int MOD = 1e9 + 7;
using namespace std;
const int N = 100001, K = 21, INF = 1e7;
vector<pair<int, int>> cg[K];
int p[N], r[N], pp[N], par[K], uw[K], cnt[N];
ll utga[K], sum[K];
int find(int v)
{
    if (p[v] != v)
        p[v] = find(p[v]);
    return p[v];
}
int merge(int u, int v)
{
    u = find(u), v = find(v);
    if (u == v)
        return 0;
    if (r[u] > r[v])
        p[v] = u;
    else
    {
        p[u] = v;
        if (r[u] == r[v])
            r[v]++;
    }
    return 1;
}
void dfs(int v, int p)
{
    par[v] = p;
    sum[v] = utga[v];
    for (auto &i : cg[v])
    {
        if (i.ff == p)
            continue;
        uw[i.ff] = (i.ss == -1 ? INF : 0);
        dfs(i.ff, v);
        sum[v] += sum[i.ff];
    }
}
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> A(m, vector<int>(3)), B(k, vector<int>(3, -1)), C, D;
    for (int i = 0; i < m; i++)
    {
        cin >> A[i][1] >> A[i][2] >> A[i][0];
        A[i][1]--;
        A[i][2]--;
    }
    sort(all(A));
    for (int i = 0; i < n; i++)
        p[i] = i;
    for (int i = 0; i < k; i++)
    {
        cin >> B[i][1] >> B[i][2];
        B[i][1]--;
        B[i][2]--;
    }
    for (auto &i : A)
        if (merge(i[1], i[2]))
            B.pb(i);
    for (int i = 0; i < n; i++)
    {
        p[i] = i;
        r[i] = 0;
    }
    for (auto &i : B)
    {
        if (merge(i[1], i[2]) && i[0] > -1)
            C.pb(i);
        else if (i[0] > -1)
            D.pb(i);
    }
    for (int i = 0; i < n; i++)
    {
        p[i] = i;
        r[i] = 0;
    }
    for (auto &i : C)
        merge(i[1], i[2]);
    vector<int> li;
    for (int i = 0; i < n; i++)
        li.pb(find(i));
    sort(all(li));
    li.resize(unique(all(li)) - li.begin());
    for (int i = 0; i < n; i++)
    {
        pp[i] = lower_bound(all(li), p[i]) - li.begin();
        cin >> cnt[i];
        utga[pp[i]] += cnt[i];
    }
    for (int i = 0; i < B.size(); i++)
    {
        B[i][1] = pp[B[i][1]];
        B[i][2] = pp[B[i][2]];
    }
    for (int i = 0; i < D.size(); i++)
    {
        D[i][1] = pp[D[i][1]];
        D[i][2] = pp[D[i][2]];
    }
    ll ans = 0;
    for (int i = 0; i < (1 << k); i++)
    {
        int ok = 0;
        for (int j = 0; j < li.size(); j++)
        {
            p[j] = j;
            r[j] = 0;
            cg[j].clear();
        }
        for (int j = 0; j < k; j++)
            if ((i & (1 << j)))
            {
                if (!merge(B[j][1], B[j][2]))
                {
                    ok = 1;
                    break;
                }
                cg[B[j][1]].pb({B[j][2], -1});
                cg[B[j][2]].pb({B[j][1], -1});
            }
        if (ok)
            continue;
        vector<vector<int>> tot;
        for (auto &i : D)
        {
            if (merge(i[1], i[2]))
            {
                cg[i[1]].pb({i[2], i[0]});
                cg[i[2]].pb({i[1], i[0]});
            }
            else
                tot.pb(i);
        }
        dfs(pp[p[0]], -1);
        for (auto &i : tot)
        {
            int v1 = i[1], v2 = i[2];
            if (sum[v1] < sum[v2])
                swap(v1, v2);
            while (v2 != v1)
            {
                uw[v2] = min(uw[v2], i[0]);
                v2 = par[v2];
            }
        }
        ll urj = 0;
        for (int i = 0; i < li.size(); i++)
            urj += uw[i] * sum[i];
        ans = max(ans, urj);
    }
    cout << ans;
}
int main()
{
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}
// 5 5 1
// 3 5 2
// 1 2 3
// 2 3 5
// 2 4 4
// 4 3 6
// 1 3
// 10 20 30 40 50

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