oj.uz

Submission #940607

# Submission time Handle Problem Language Result Execution time Memory
940607 2024-03-07T11:34:30 Z danikoynov Toll (APIO13_toll) C++14
78 / 100
 2500 ms 22520 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];

int can_use[maxn];
void dfs(int v, int p, int tag)
{
    used[v] = tag;
    for (pair < int, int > nb : adj[v])
    {
        if (nb.first == p || !can_use[nb.second])
            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 || !can_use[nb.second])
            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 i = 0; i < k; i ++)
    {
        adj[greed[i].v].push_back({greed[i].u, i + m + 1});
        adj[greed[i].u].push_back({greed[i].v, i + m + 1});
    }
    for (int i = 1; i <= m; i ++)
    {
        adj[roads[i].v].push_back({roads[i].u, i});
        adj[roads[i].u].push_back({roads[i].v, i});
    }

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

        for (int i = 1; i <= n; i ++)
        {
            par[i] = i;

        }

        for (int i = 1; i <= m + k; i ++)
            can_use[i] = 0;

        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;
            }
            can_use[m + j + 1] = 1;
            //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))
            {
                can_use[i] = 1;
                //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:270:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  270 |     for (int i = 0; i < fin.size(); i ++)
      |                     ~~^~~~~~~~~~~~
toll.cpp:276:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  276 |     for (int i = 0; i < fin.size(); i ++)
      |                     ~~^~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13400 KB Output is correct
2 Correct 2 ms 13404 KB Output is correct
3 Correct 4 ms 13404 KB Output is correct
4 Correct 4 ms 13404 KB Output is correct
5 Correct 6 ms 13656 KB Output is correct
6 Correct 5 ms 13660 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13400 KB Output is correct
2 Correct 2 ms 13404 KB Output is correct
3 Correct 4 ms 13404 KB Output is correct
4 Correct 4 ms 13404 KB Output is correct
5 Correct 6 ms 13656 KB Output is correct
6 Correct 5 ms 13660 KB Output is correct
7 Correct 188 ms 19068 KB Output is correct
8 Correct 204 ms 22520 KB Output is correct
9 Correct 195 ms 21372 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13400 KB Output is correct
2 Correct 2 ms 13404 KB Output is correct
3 Correct 4 ms 13404 KB Output is correct
4 Correct 4 ms 13404 KB Output is correct
5 Correct 6 ms 13656 KB Output is correct
6 Correct 5 ms 13660 KB Output is correct
7 Correct 188 ms 19068 KB Output is correct
8 Correct 204 ms 22520 KB Output is correct
9 Correct 195 ms 21372 KB Output is correct
10 Execution timed out 2571 ms 18300 KB Time limit exceeded
11 Halted 0 ms 0 KB -