oj.uz

Submission #940568

# Submission time Handle Problem Language Result Execution time Memory
940568 2024-03-07T10:49:24 Z Ice_man Toll (APIO13_toll) C++14
56 / 100
 2500 ms 30548 KB 
#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.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 5 ms 14684 KB Output is correct
5 Correct 178 ms 14948 KB Output is correct
6 Correct 107 ms 14940 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 5 ms 14684 KB Output is correct
5 Correct 178 ms 14948 KB Output is correct
6 Correct 107 ms 14940 KB Output is correct
7 Execution timed out 2559 ms 30548 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 5 ms 14684 KB Output is correct
5 Correct 178 ms 14948 KB Output is correct
6 Correct 107 ms 14940 KB Output is correct
7 Execution timed out 2559 ms 30548 KB Time limit exceeded
8 Halted 0 ms 0 KB -