oj.uz

답안 #1062048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1062048 2024-08-16T17:45:17 Z underwaterkillerwhale 통행료 (APIO13_toll) C++17
100 / 100
 1870 ms 20408 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) vector<int> ().swap(adj[i]), 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 4 ms 10584 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 4 ms 10584 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 4 ms 10584 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 137 ms 18612 KB Output is correct
8 Correct 158 ms 18812 KB Output is correct
9 Correct 141 ms 19120 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 4 ms 10584 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 137 ms 18612 KB Output is correct
8 Correct 158 ms 18812 KB Output is correct
9 Correct 141 ms 19120 KB Output is correct
10 Correct 1230 ms 20408 KB Output is correct
11 Correct 1870 ms 18876 KB Output is correct
12 Correct 1847 ms 19384 KB Output is correct