Submission #220090

#	Time	Username	Problem	Language	Result	Execution time	Memory
220090		osaaateiasavtnl	Toll (APIO13_toll)	C++14	100 / 100	2041 ms	22312 KiB

toll

#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) {
            //cout << "go " << u << ' ' << e.f << ' ' << e.s << endl;
            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});
                //cout << "edge " << u << ' ' << v << ' ' << 1 << endl;
            }   
        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});               
                //cout << "edge " << e.u << ' ' << e.v << ' ' << 0 << endl;
            }                   
        }   
        dfs(troot, troot);
        /*
        cout << "up : ";
        for (int i = 1; i <= ptr; ++i)
            cout << up[i] << ' ';
        cout << endl;
        */
        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);
            }
        }   
        //cout << "mask " << mask << endl;
        int nn = 0;
        for (int i = 1; i <= ptr; ++i)
            if (i != troot) {
                //cout << i << ' ' << cnt[i] << ' ' << up[i] << endl;
                nn += cnt[i] * up[i];
            }
        ans = max(ans, nn);
    }   
    cout << ans << endl;
}   

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22