oj.uz

Submission #940334

# Submission time Handle Problem Language Result Execution time Memory
940334 2024-03-07T08:12:09 Z danikoynov Toll (APIO13_toll) C++14
56 / 100
 2500 ms 17600 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10, maxm = 3e5 + 10, maxk = 21;
const ll inf = 1e18;

struct edge
{
    int v, u;
    ll w;

    edge(int _v = 0, int _u = 0, ll _w = 0)
    {
        v = _v;
        u = _u;
        w = _w;
    }

    bool operator < (const edge &e) const
    {
        return w < e.w;
    }
}roads[maxm];


bool cmp_w(const edge &e1, const edge &e2)
{
    return e1.w < e2.w;
}

edge greed[maxk];
int n, m, k;
ll d[maxn];

void input()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i ++)
        cin >> roads[i].v >> roads[i].u >> roads[i].w;
    for (int i = 0; i < k; i ++)
        cin >> greed[i].v >> greed[i].u;
    for (int i = 1; i <= n; i ++)
        cin >> d[i];
}

int par[maxn];

int find_leader(int v)
{
    if (v == par[v])
        return v;
    return (par[v] = find_leader(par[v]));
}

bool unite(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);

    if (v == u)
        return false;
    par[u] = v;
    ///cout << "return true" << endl;
    return true;
}

vector < pair < int, int > > adj[maxn];
int used[maxn];

void dfs(int v, int p, int tag)
{
    used[v] = tag;
    for (pair < int, int > nb : adj[v])
    {
        if (nb.first == p)
            continue;
        dfs(nb.first, v, tag);
    }
}

ll sub[maxn], cost[maxk];
ll calc(int v, int p)
{
    sub[v] = d[v];
    ll res = 0;
    for (pair < int, int > nb : adj[v])
    {
        if (nb.first == p)
            continue;
        res += calc(nb.first, v);
        sub[v] += sub[nb.first];
        if (nb.second != -1)
        {
            res = res + sub[nb.first] * cost[nb.second];
        }
    }
    return res;
}
void brute_force()
{

    ll res = 0;
    for (int mask = 0; mask < (1 << k); mask ++)
    {

        for (int i = 1; i <= n; i ++)
        {
            par[i] = i;
            adj[i].clear();
        }

        bool done = false;
        for (int j = 0; j < k; j ++)
        {
            if ((mask & (1 << j)) == 0)
                continue;
            ///cout << find_leader(greed[j].v) << " : " << find_leader(greed[j].u) << endl;
            if (unite(greed[j].v, greed[j].u) == false)
            {

                done = true;
                break;
            }

            adj[greed[j].v].push_back({greed[j].u, j});
            adj[greed[j].u].push_back({greed[j].v, j});
        }

        if (done)
            continue;

        for (int i = 1; i <= m; i ++)
        {
            if (unite(roads[i].v, roads[i].u))
            {
                adj[roads[i].v].push_back({roads[i].u, - 1});
                adj[roads[i].u].push_back({roads[i].v, - 1});
            }
        }

        for (int j = 0; j < k; j ++)
        {
            if ((mask & (1 << j)) == 0)
                continue;
            for (int i = 1; i <= n; i ++)
                used[i] = 0;
            dfs(greed[j].v, greed[j].u, 1);
            dfs(greed[j].u, greed[j].v, 2);
            /**for (int i = 1; i <= n; i ++)
                cout << used[i] << " ";
            cout << endl;*/
            ll price = inf;
            for (int i = 1; i <= m; i ++)
            {
                if (used[roads[i].v] != used[roads[i].u])
                    price = min(price, roads[i].w);
            }
            ///cout << "price " << price << endl;
            cost[j] = price;
        }

        ll cur = calc(1, -1);
        res = max(res, cur);
    }

    cout << res << endl;
}


void preprocess()
{
    sort(roads + 1, roads + m + 1, cmp_w);
}
void solve()
{
    input();
    preprocess();
    brute_force();
}

int main()
{
    speed();
    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

5 6 1
1 5 3
5 4 2
4 3 6
3 2 3
1 3 7
1 2 2
5 3
1 1 1 1 1
*/

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9560 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9560 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Correct 5 ms 9564 KB Output is correct
4 Correct 4 ms 9564 KB Output is correct
5 Correct 153 ms 9560 KB Output is correct
6 Correct 106 ms 9704 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9560 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Correct 5 ms 9564 KB Output is correct
4 Correct 4 ms 9564 KB Output is correct
5 Correct 153 ms 9560 KB Output is correct
6 Correct 106 ms 9704 KB Output is correct
7 Execution timed out 2554 ms 17600 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9560 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Correct 5 ms 9564 KB Output is correct
4 Correct 4 ms 9564 KB Output is correct
5 Correct 153 ms 9560 KB Output is correct
6 Correct 106 ms 9704 KB Output is correct
7 Execution timed out 2554 ms 17600 KB Time limit exceeded
8 Halted 0 ms 0 KB -