oj.uz

Submission #1062047

# Submission time Handle Problem Language Result Execution time Memory
1062047 2024-08-16T17:42:24 Z underwaterkillerwhale Toll (APIO13_toll) C++17
100 / 100
 1041 ms 39576 KB 
#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

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.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 3 ms 22876 KB Output is correct
3 Correct 4 ms 23052 KB Output is correct
4 Correct 5 ms 22876 KB Output is correct
5 Correct 7 ms 23128 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 3 ms 22876 KB Output is correct
3 Correct 4 ms 23052 KB Output is correct
4 Correct 5 ms 22876 KB Output is correct
5 Correct 7 ms 23128 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 117 ms 31996 KB Output is correct
8 Correct 127 ms 39268 KB Output is correct
9 Correct 129 ms 39576 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 3 ms 22876 KB Output is correct
3 Correct 4 ms 23052 KB Output is correct
4 Correct 5 ms 22876 KB Output is correct
5 Correct 7 ms 23128 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 117 ms 31996 KB Output is correct
8 Correct 127 ms 39268 KB Output is correct
9 Correct 129 ms 39576 KB Output is correct
10 Correct 713 ms 38356 KB Output is correct
11 Correct 1041 ms 39092 KB Output is correct
12 Correct 1012 ms 39348 KB Output is correct