oj.uz

Submission #220091

# Submission time Handle Problem Language Result Execution time Memory
220091 2020-04-06T23:43:41 Z osaaateiasavtnl Toll (APIO13_toll) C++17
100 / 100
 2047 ms 17280 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 3e5 + 7, K = 23, INF = 1e9 + 7;
struct Edge { int u, v, c; bool in; };  
bool comp(Edge a, Edge b) { return a.c < b.c; }
int root(int u, int *par) {
    if (par[u] == u) return u;
    else return par[u] = root(par[u], par);
}   
int par[N], par1[N], w[N], num[N], ww[K];
int n, m, k;
bool in[N];
int small_par[K];
vector <pair <int, bool> > g[K];
int tree_par[K];
int h[K], cnt[K], up[K];
void dfs(int u, int p) {
    tree_par[u] = p;
    cnt[u] = ww[u];
    for (auto e : g[u]) {
        int v = e.f;
        if (v != p) {
            h[v] = h[u] + 1;
            if (e.s)
                up[v] = INF;
            else
                up[v] = 0;
            dfs(v, u);
            cnt[u] += cnt[v];
        }   
    }
}   
void getup(int &u, int c) {
    up[u] = min(up[u], c);
    u = tree_par[u];
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m >> k;
    vector <Edge> ev;
    for (int i = 0; i < m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        ev.app({u, v, c, 0});
    }   
    sort(all(ev), comp);
    for (int i = 1; i <= n; ++i) par[i] = i;
    for (auto &e : ev) {
        if (root(e.u, par) != root(e.v, par)) {
            e.in = 1;
            par[root(e.u, par)] = root(e.v, par);
        }   
    }   
    for (int i = 1; i <= n; ++i) par[i] = par1[i] = i;
    vector <ii> add;
    for (int i = 0; i < k; ++i) {
        int u, v; cin >> u >> v;
        add.app(mp(u, v));
        if (root(u, par) != root(v, par))
            par[root(u, par)] = root(v, par);
    }   
    vector <Edge> small;
    for (auto &e : ev) {
        if (root(e.u, par) != root(e.v, par)) {
            par[root(e.u, par)] = root(e.v, par);
            par1[root(e.u, par1)] = root(e.v, par1);
        }
        else if (e.in) 
            small.app(e);
    }   
    int ptr = 0;
    for (int i = 1; i <= n; ++i)
        if (par1[i] == i)
            num[i] = ++ptr;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        ww[num[root(i, par1)]] += w[i];
    }
    int troot = num[root(1, par1)];
    sort(all(small), comp);
    for (auto &e : small) {
        e.u = num[root(e.u, par1)];
        e.v = num[root(e.v, par1)];
    }   
    for (auto &e : add) {
        e.f = num[root(e.f, par1)];
        e.s = num[root(e.s, par1)];
    }   
    int ans = 0;
    for (int mask = 0; mask < (1 << k); ++mask) {
        for (int i = 0; i < K; ++i) {
            small_par[i] = i;
            g[i].clear();
        }
        bool cyc = 0;
        for (int i = 0; i < k; ++i)
            if ((mask >> i) & 1) {
                int u = add[i].f, v = add[i].s;
                if (root(u, small_par) == root(v, small_par)) {
                    cyc = 1;
                    break;
                }   
                small_par[root(u, small_par)] = root(v, small_par);
                g[u].app({v, 1}); g[v].app({u, 1});
            }   
        if (cyc)
            continue;
        vector <Edge> rel;                                        
        for (auto e : small) {
            if (root(e.u, small_par) == root(e.v, small_par)) 
                rel.app(e);
            else {
                small_par[root(e.u, small_par)] = root(e.v, small_par);
                g[e.u].app({e.v, 0}); g[e.v].app({e.u, 0});               
            }                   
        }   
        dfs(troot, troot);
        for (auto e : rel) {
            int u = e.u, v = e.v;
            while (h[u] > h[v]) 
                getup(u, e.c);
            while (h[v] > h[u]) 
                getup(v, e.c);
            while (u != v) {
                getup(u, e.c);
                getup(v, e.c);
            }
        }   
        int nn = 0;
        for (int i = 1; i <= ptr; ++i)
            if (i != troot) 
                nn += cnt[i] * up[i];
        ans = max(ans, nn);
    }   
    cout << ans << endl;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 8 ms 896 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 293 ms 17108 KB Output is correct
8 Correct 275 ms 17108 KB Output is correct
9 Correct 276 ms 17280 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 293 ms 17108 KB Output is correct
8 Correct 275 ms 17108 KB Output is correct
9 Correct 276 ms 17280 KB Output is correct
10 Correct 1721 ms 17108 KB Output is correct
11 Correct 2047 ms 17236 KB Output is correct
12 Correct 2001 ms 17108 KB Output is correct