oj.uz

답안 #489849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
489849 2021-11-24T23:36:27 Z JerryLiu06 통행료 (APIO13_toll) C++17
100 / 100
 1626 ms 8176 KB 
// https://oj.uz/problem/view/APIO13_toll
 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0);
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert 
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
 
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
template<class T> void remDup(vector<T>& v) { sor(v); v.erase(unique(all(v)), v.end()); }
 
const int MOD = 1e9 + 7;
const int MX = 1e5 + 10;
const ll INF = 1e18;
 
int N, M, K, comp[MX]; vector<array<int, 3>> ed, add; vpi nxt;
 
ll compSz[22]; ll ans = 0, res = 0;
 
vpi adj[22]; int dep[22]; pi par[22];
 
template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
 
    void init() { 
        F0R(i, SZ) {
            par[i] = i;
            sz[i] = 1;
        }
    }
    int find(int A) {
        return A == par[A] ? A : (par[A] = find(par[A]));
    }
    bool onion(int A, int B) {
        A = find(A);
        B = find(B);
 
        if (A == B) {
            return false;
        }
        if (sz[A] < sz[B]) {
            swap(A, B);
        }
        par[B] = A;
        sz[A] += sz[B];
 
        return true;
    }
};
 
void DFS1(int X) {
    EACH(Y, adj[X]) if (Y.f != par[X].f) {  
        dep[Y.f] = dep[X] + 1;
        par[Y.f] = {X, Y.s};
        
        DFS1(Y.f);
    }
}
void markEdges(array<int, 3> E) {
    int A = E[1], B = E[2];
 
    while (A != B) {
        if (dep[A] < dep[B]) swap(A, B);
 
        ckmin(par[A].s, E[0]);
        A = par[A].f;
    }
}
void DFS2(int X, ll cost) {
    res += compSz[X] * cost;
 
    EACH(Y, adj[X]) if (Y.f != par[X].f) {
        DFS2(Y.f, cost + par[Y.f].s);
    }
}
 
void solve(int msk) {
    DSU<22> D; D.init();
 
    FOR(i, 1, K + 2) {
        adj[i].clear();
    }
    F0R(i, K) {
        if (msk & (1 << i)) {
            if (!D.onion(nxt[i].f, nxt[i].s)) {
                return ;
            } 
            adj[nxt[i].f].pb({nxt[i].s, MOD});
            adj[nxt[i].s].pb({nxt[i].f, MOD});
        }
    }
    vector<array<int, 3>> bad;
 
    EACH(E, add) {
        if (!D.onion(E[1], E[2])) {
            bad.pb(E);
        }
        else {
            adj[E[1]].pb({E[2], 0});
            adj[E[2]].pb({E[1], 0});
        }
    }
    DFS1(1);
    
    EACH(E, bad) {
        markEdges(E);
    }
    res = 0;
 
    DFS2(1, 0);
    
    ckmax(ans, res);
}
 
int main() {
    FASTIO;
 
    cin >> N >> M >> K; 
 
    F0R(i, M) {
        int A, B, C;
        cin >> A >> B >> C;
 
        ed.pb({C, A, B});
    }
    sor(ed);
 
    DSU<MX> D1, D2; // original, new
    
    D1.init(), D2.init();
 
    F0R(i, K) {
        int A, B; cin >> A >> B;
 
        nxt.pb({A, B});
        D2.onion(A, B);
    }
    EACH(E, ed) {
        // Guaranteed to be in MST
        if (D2.find(E[1]) != D2.find(E[2])) {
            D1.onion(E[1], E[2]);
            D2.onion(E[1], E[2]);
        }
        // May create cycle with new edges
    }
    map<int, int> MP; int numComp = 0;
 
    FOR(i, 1, N + 1) {
        int P; cin >> P;
 
        int curPar = D1.find(i);
        
        if (!MP.count(curPar)) {
            MP[curPar] = ++numComp;
        }
        comp[i] = MP[curPar];
        compSz[comp[i]] += P; 
    }
    EACH(E, ed) {
        if (D1.onion(E[1], E[2])) {
            add.pb(E);
        }
    }
    EACH(E, nxt) {
        E.f = comp[E.f];
        E.s = comp[E.s];
    }
    EACH(E, add) {
        E[1] = comp[E[1]];
        E[2] = comp[E[2]];
    }
    F0R(msk, (1 << K)) {
        solve(msk);
    }
    cout << ans;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 3 ms 1996 KB Output is correct
6 Correct 3 ms 1996 KB Output is correct
7 Correct 161 ms 8048 KB Output is correct
8 Correct 176 ms 8176 KB Output is correct
9 Correct 152 ms 8072 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 3 ms 1996 KB Output is correct
6 Correct 3 ms 1996 KB Output is correct
7 Correct 161 ms 8048 KB Output is correct
8 Correct 176 ms 8176 KB Output is correct
9 Correct 152 ms 8072 KB Output is correct
10 Correct 1151 ms 8108 KB Output is correct
11 Correct 1626 ms 8112 KB Output is correct
12 Correct 1612 ms 8080 KB Output is correct