oj.uz

Submission #1062050

# Submission time Handle Problem Language Result Execution time Memory
1062050 2024-08-16T17:45:44 Z underwaterkillerwhale Toll (APIO13_toll) C++17
100 / 100
 1010 ms 20424 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 = 1e5 + 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[(int)3e5 + 7];

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] = 1e6 + 7, 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 += dp[v] * mn[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:115:38: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  115 |         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:142:38: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  142 |         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 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 119 ms 20152 KB Output is correct
8 Correct 119 ms 20400 KB Output is correct
9 Correct 115 ms 20424 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 119 ms 20152 KB Output is correct
8 Correct 119 ms 20400 KB Output is correct
9 Correct 115 ms 20424 KB Output is correct
10 Correct 738 ms 18616 KB Output is correct
11 Correct 1010 ms 19380 KB Output is correct
12 Correct 1002 ms 20152 KB Output is correct