Submission #940568

#	Time	Username	Problem	Language	Result	Execution time	Memory
940568		Ice_man	Toll (APIO13_toll)	C++14	56 / 100	2559 ms	30548 KiB

toll

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>

#define maxn 200005
#define maxm 300005
#define maxlog 20
#define INF 1000000000000000005
#define mod 998244353
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;


long long parent[maxn], sz[maxn];

long long find_parent(long long node)
{
    return node == parent[node]? node : parent[node] = find_parent(parent[node]);
}


bool unite(long long a, long long b)
{
    a = find_parent(a);
    b = find_parent(b);

    if(a == b)
        return false;

    /**if(sz[b] > sz[a])
        swap(a, b);*/

    //sz[a] += sz[b];
    parent[b] = parent[a];

    return true;
}

struct edge
{
    long long from, to;
    long long c;

    edge() {};
    edge(long long _from, long long _to, long long _c)
    {
        from = _from;
        to = _to;
        c = _c;
    }

    bool operator <(const edge &a)const
    {
        return c < a.c;
    }
};


long long n, m, k;

edge edges[maxm], new_edges[21];

long long used[maxn];
long long c[maxn];
vector <pair <long long, long long>> v[maxn];

void read()
{
    cin >> n >> m;
    cin >> k;

    for(long long i = 1; i <= m; i++)
        cin >> edges[i].from >> edges[i].to >> edges[i].c;

    for(long long i = 0; i < k; i++)
        cin >> new_edges[i].from >> new_edges[i].to;

    for(int i = 0; i < k; i++)
        new_edges[i].c = 0;

    for(long long i = 1; i <= n; i++)
        cin >> c[i];
}

long long sub_sz[maxn];
long long c2[21];

long long co(long long node, long long _parent)
{
    sub_sz[node] = c[node];
    long long pom = 0;

    for(pair <long long, long long> nb : v[node])
    {
        if(nb.X == _parent)
            continue;

        pom += co(nb.X, node);
        sub_sz[node] += sub_sz[nb.X];

        if(nb.Y != -1)
            pom = pom + sub_sz[nb.X] * c2[nb.Y];

    }

    return pom;
}




long long paint;

void dfs(long long node, long long _parent)
{
    used[node] = paint;

    for(pair <long long, long long> nb : v[node])
    {
        if(nb.X == _parent)
            continue;

        dfs(nb.X, node);
    }
}

long long ans = 0;
bool finished = false;

void _clear()
{
    finished = false;
    for(long long i = 1; i <= n; i++)
    {
        parent[i] = i;
        sz[i] = 1;
        v[i].clear();
    }
}

void reset_used()
{
    for(long long i = 1; i <= n; i++)
        used[i] = 0;
}

long long pom = 0;

void check(long long mask)
{
    for(long long i = 0; i < k; i++)
    {
        if((mask & (1 << i)) == 0)
            continue;

        reset_used();

        paint  = 1;
        dfs(new_edges[i].from , new_edges[i].to);

        paint = 2;
        dfs(new_edges[i].to , new_edges[i].from);

        pom = INF;
        for(long long j = 1; j <= m; j++)
            if(used[edges[j].from] != used[edges[j].to])
                pom = min(pom , edges[j].c);

        c2[i] = pom;
    }

}

bool compare(edge a , edge b)
{
    return a.c < b.c;
}


void solve()
{

    sort(edges + 1 , edges + 1 + m , compare);

    for(long long mask = 0; mask < (1 << k); mask++)
    {
        _clear();

        for(long long i = 0; i < k; i++)
        {
            if((mask & (1 << i)) == 0)
                continue;

            bool pom = unite(new_edges[i].from, new_edges[i].to);

            if(pom == false)
            {
                finished = true;
                break;
            }

            v[new_edges[i].from].push_back({new_edges[i].to, i});
            v[new_edges[i].to].push_back({new_edges[i].from, i});

        }

        if(finished == true)
            continue;

        for(long long i = 1; i <= m; i++)
            if(unite(edges[i].from, edges[i].to) == true)
            {
                v[edges[i].from].push_back({edges[i].to , -1});
                v[edges[i].to].push_back({edges[i].from , -1});
            }

        check(mask);

        long long help = co(1 , -1);

        ans = max(ans , help);

        ///cout << ans << endl;

    }

    cout << ans << endl;
}




int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);


    read();
    solve();



    return 0;
}

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