oj.uz

Submission #940614

# Submission time Handle Problem Language Result Execution time Memory
940614 2024-03-07T11:40:23 Z danikoynov Toll (APIO13_toll) C++14
100 / 100
 2175 ms 27424 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[v] = u;
    ///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 > m)
        {
            res = res + sub[nb.first] * cost[nb.second - m - 1];
        }
    }
    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, m + j + 1});
            adj[greed[j].u].push_back({greed[j].v, m + j + 1});
        }

        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, i});
                adj[roads[i].u].push_back({roads[i].v, i});
            }
        }

        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);
}

vector < int > graph[maxn];
int marked[maxn];
ll population[maxn];
void trav(int v, int p, int s)
{
    marked[v] = s;
    population[s] += d[v];
    for (int u : graph[v])
    {
        if (u == p)
            continue;
        trav(u, v, s);
    }
}

vector < edge > maybe;
void compress_tree()
{
    for (int i = 1; i <= n; i ++)
    {
        par[i] = i;
    }
    for (int i = 0; i < k; i ++)
    {
        unite(greed[i].v, greed[i].u);
    }

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

    int cp_cnt = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (!marked[i])
        {
            cp_cnt ++;
            trav(i, -1, cp_cnt);
        }
    }

    vector < edge > fin;
    for (int i = 1; i <= m; i ++)
    {
        edge cur = roads[i];
        if (marked[cur.v] != marked[cur.u])
            fin.push_back(edge(marked[cur.v], marked[cur.u], cur.w));
    }


    for (int i = 0; i < k; i ++)
    {
        greed[i].v = marked[greed[i].v];
        greed[i].u = marked[greed[i].u];
    }
    n = cp_cnt;
    for (int i = 1; i <= n; i ++)
        d[i] = population[i];

    for (int i = 1; i <= n; i ++)
    par[i] = i;
    sort(fin.begin(), fin.end(), cmp_w);
    vector < edge > vec;
    for (int i = 0; i < fin.size(); i ++)
    {
        if (unite(fin[i].v, fin[i].u))
            vec.push_back(fin[i]);
    }
    fin = vec;
    for (int i = 0; i < fin.size(); i ++)
    {
        roads[i + 1] = fin[i];
    }
    m = fin.size();

    //cout << "new n " << n << endl;
    //cout << "new m " << m << endl;
    /**for (int i = 1; i <= n; i ++)
        cout << d[i] << " ";
    cout << endl;*/
}
void solve()
{
    input();
    preprocess();
    compress_tree();
    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
*/

Compilation message

toll.cpp: In function 'void compress_tree()':
toll.cpp:255:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  255 |     for (int i = 0; i < fin.size(); i ++)
      |                     ~~^~~~~~~~~~~~
toll.cpp:261:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  261 |     for (int i = 0; i < fin.size(); i ++)
      |                     ~~^~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13148 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 3 ms 12984 KB Output is correct
5 Correct 4 ms 13148 KB Output is correct
6 Correct 5 ms 13148 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13148 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 3 ms 12984 KB Output is correct
5 Correct 4 ms 13148 KB Output is correct
6 Correct 5 ms 13148 KB Output is correct
7 Correct 141 ms 18680 KB Output is correct
8 Correct 171 ms 22852 KB Output is correct
9 Correct 183 ms 21128 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13148 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 3 ms 12984 KB Output is correct
5 Correct 4 ms 13148 KB Output is correct
6 Correct 5 ms 13148 KB Output is correct
7 Correct 141 ms 18680 KB Output is correct
8 Correct 171 ms 22852 KB Output is correct
9 Correct 183 ms 21128 KB Output is correct
10 Correct 1422 ms 17900 KB Output is correct
11 Correct 2175 ms 20932 KB Output is correct
12 Correct 1963 ms 27424 KB Output is correct