Submission #1062047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062047		underwaterkillerwhale	Toll (APIO13_toll)	C++17	100 / 100	1041 ms	39576 KiB

toll

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 3e5 + 2;
const int Mod = 1e9 + 7;
const int INF = 2e9 + 7;
const ll BASE = 137;
const int szBL = 320;

struct Disjoin_set {
    int lab[N], sz[N];

    void init (int n) {
        rep (i, 1, n) lab[i] = i, sz[i] = 1;
    }
    int Find (int u) {
        return u == lab[u] ? u : lab[u] = Find(lab[u]);
    }
    bool Join (int u, int v)  {
        if ((u = Find(u)) == (v = Find(v))) return 0;
        if (sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        lab[v] = u;
        return 1;
    }
}DSU;

struct Edge {
    int u, v, w, id;
};

int n, m, K;
int P[N];
pii nroad[N];
vector<int> ke[N], adj[N];
vector<Edge> delE;
bool inE[N];

ll cnt[N];
int num_cpn, cpn[N];

int mn[N], dd[N];
ll dp[N];
int high[N], par[N];

void solution () {
    cin >> n >> m >> K;
    vector<Edge> edges;
    rep (i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.pb({u, v, w, i});
    }
    DSU.init(n);
    sort (ALL(edges), [] (Edge u, Edge v) { return u.w < v.w; });
    ll MST = 0;
    iter (&E, edges)
        if (DSU.Join(E.u, E.v)) inE[E.id] = 1;
    rep (i, 1, K) cin >> nroad[i].fs >> nroad[i].se;
    rep (i, 1, n) cin >> P[i];
    DSU.init(n);
    rep (i, 1, K) {
        DSU.Join(nroad[i].fs, nroad[i].se);
    }
    iter (&E, edges) if (DSU.Join(E.u, E.v) == 0) {
        if (inE[E.id] == 1) delE.pb(E);
        inE[E.id] = 0;
    }
    iter (&E, edges) if (inE[E.id] == 1) {
        ke[E.u].pb(E.v);
        ke[E.v].pb(E.u);
    }
    function<void(int, int)> pdfs = [&] (int u, int p) {
        cnt[num_cpn] += P[u];
        cpn[u] = num_cpn;
        iter (&v, ke[u]) {
            if (v == p) continue;
            pdfs (v, u);
        }
    };
    rep (i, 1, n) {
        if (cpn[i]) continue;
        ++num_cpn;
        pdfs(i, 0);
    }
    rep (i, 1, K) {
        nroad[i].fs = cpn[nroad[i].fs];
        nroad[i].se = cpn[nroad[i].se];
    }
    iter (&E, delE) {
        E.u = cpn[E.u];
        E.v = cpn[E.v];
    }
    ll res = 0;
    function<void(int)> solve = [&] (int msk) {
        DSU.init(num_cpn);
        rep (i, 1, num_cpn) {
            adj[i].clear();
            mn[i] = INF, dd[i] = 0, dp[i] = 0;
        }
        rep (i, 1, K) if (bit(msk, i - 1)) {
            if (DSU.Join(nroad[i].fs, nroad[i].se) == 0) return;
            adj[nroad[i].fs].pb(nroad[i].se);
            adj[nroad[i].se].pb(nroad[i].fs);
        }
        static vector<Edge> curE; curE.clear();
        iter (&E, delE) {
            if (DSU.Join (E.u, E.v) == 0) curE.pb(E);
            else {
                adj[E.u].pb(E.v);
                adj[E.v].pb(E.u);
            }
        }
        function<void(int, int)> pdfs2 = [&] (int u, int p) {
            high[u] = high[p] + 1;
            par[u] = p;
            iter (&v, adj[u]) if (v != p) pdfs2 (v, u);
        };
        pdfs2 (1, 0);
        iter (&E, curE) {
            int u = E.u, v = E.v, val = E.w;
            while (u != v) {
                if (high[u] > high[v]) swap(u, v);
                mn[v] = min(mn[v], val);
                v = par[v];
            }
        }
        rep (i, 1, K) if (bit(msk, i - 1)) {
            if (high[nroad[i].fs] > high[nroad[i].se]) swap(nroad[i].fs, nroad[i].se);
            dd[nroad[i].se] = 1;
        }
        ll curcost = 0;
        function<void(int,int)> dfs2 = [&] (int u, int p) {
            dp[u] = cnt[u];
            iter (&v, adj[u]) {
                if (v == p) continue;
                dfs2 (v, u);
                dp[u] += dp[v];
                if (dd[v]) {
                    curcost += 1LL * mn[v] * dp[v];
                }
            }
        };
        dfs2(1, 0);
        res = max(res, curcost);
    };
    rep (msk, 1, (1 << K) - 1) solve(msk);
    cout << res <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +2
2 + 8 * 2 - 9
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
*/

Compilation message (stderr)

toll.cpp: In lambda function:
toll.cpp:118:38: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  118 |         rep (i, 1, K) if (bit(msk, i - 1)) {
      |                                    ~~^~~
toll.cpp:10:30: note: in definition of macro 'bit'
   10 | #define bit(msk, i) ((msk >> i) & 1)
      |                              ^
toll.cpp:145:38: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  145 |         rep (i, 1, K) if (bit(msk, i - 1)) {
      |                                    ~~^~~
toll.cpp:10:30: note: in definition of macro 'bit'
   10 | #define bit(msk, i) ((msk >> i) & 1)
      |                              ^
toll.cpp: In function 'void solution()':
toll.cpp:73:8: warning: unused variable 'MST' [-Wunused-variable]
   73 |     ll MST = 0;
      |        ^~~

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