oj.uz

답안 #489851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
489851 2021-11-24T23:48:33 Z JerryLiu06 통행료 (APIO13_toll) C++17
100 / 100
 1741 ms 8180 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[25]; vpi adj[25]; map<int, int> MP; int numComp = 0;

int dep[25]; pi par[25]; ll sub[25]; ll ans = 0, res = 0;
 
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, int P) {
    EACH(Y, adj[X]) if (Y.f != P) {  
        dep[Y.f] = dep[X] + 1;
        par[Y.f] = {X, Y.s};
        
        DFS1(Y.f, X);
    }
}
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, int P) {
    sub[X] = compSz[X];
 
    EACH(Y, adj[X]) if (Y.f != P) {
        DFS2(Y.f, X);

        sub[X] += sub[Y.f];

        res += sub[Y.f] * par[Y.f].s;
    }
}
 
void solve(int msk) {
    DSU<25> D; D.init();
 
    FOR(i, 1, numComp + 1) {
        adj[i].clear();
    }
    F0R(i, K) {
        if (msk & (1 << i)) {
            if (D.find(nxt[i].f) == D.find(nxt[i].s)) {
                return ;
            } 
            D.onion(nxt[i].f, nxt[i].s);

            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.find(E[1]) == D.find(E[2])) {
            bad.pb(E); continue;
        }
        D.onion(E[1], E[2]);

        adj[E[1]].pb({E[2], 0});
        adj[E[2]].pb({E[1], 0});
    }
    DFS1(1, 0);
    
    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]);
        }
    } 
    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) {
        // May create cycle with new edges
        if (D1.find(E[1]) != D1.find(E[2])) {
            add.pb(E); D1.onion(E[1], E[2]);
        }
    }
    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 147 ms 8116 KB Output is correct
8 Correct 166 ms 8180 KB Output is correct
9 Correct 161 ms 8108 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 147 ms 8116 KB Output is correct
8 Correct 166 ms 8180 KB Output is correct
9 Correct 161 ms 8108 KB Output is correct
10 Correct 1281 ms 8148 KB Output is correct
11 Correct 1741 ms 8040 KB Output is correct
12 Correct 1728 ms 8120 KB Output is correct