oj.uz

답안 #948221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948221 2024-03-17T23:05:46 Z parlimoos 통행료 (APIO13_toll) C++14
100 / 100
 1470 ms 18100 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , m , k , ps[21] , tms[21][2];
vector<arr(3)> mst , cnds , dts;
vector<ll> a;
vector<int> g[21];
vector<arr(2)> adds;
ll dsu[100000][2] , mem[21];
bool iscnd[100000];
int rt;

void init(){
    for(int v = 0 ; v < n ; v++) dsu[v][0] = -1 , dsu[v][1] = a[v];
}
int findDsu(int v){
    if(dsu[v][0] == -1) return v;
    return (dsu[v][0] = findDsu(dsu[v][0]));
}
void uDsu(int a , int b){
    a = findDsu(a) , b = findDsu(b);
    if(a == b) return;
    dsu[a][1] += dsu[b][1] , dsu[b][0] = a;
}
void getCnds(){
    for(auto &e : adds) uDsu(e[0] , e[1]);
    int cnt = 0;
    for(int e = 0 ; e < n - 1 ; e++){
        if(findDsu(mst[e][1]) == findDsu(mst[e][2])) cnds.pb(mst[e]) , iscnd[e] = 1;
        else uDsu(mst[e][1] , mst[e][2]);
    }
    init();
    for(int e = 0 ; e < n - 1 ; e++){
        if(!iscnd[e]) uDsu(mst[e][1] , mst[e][2]);
    }
    int inxs[100000];
    cnt = 0 , a.cl();
    for(int v = 0 ; v < n ; v++){
        if(findDsu(v) != v) continue;
        inxs[v] = cnt++ , a.pb(dsu[v][1]);
    }
    rt = inxs[findDsu(0)];
    for(int e = 0 ; e < (int)cnds.size() ; e++){
        cnds[e][1] = inxs[findDsu(cnds[e][1])] , cnds[e][2] = inxs[findDsu(cnds[e][2])];
        dts.pb({0 , cnds[e][1] , cnds[e][2]});
    }
    for(int e = 0 ; e < k ; e++){
        adds[e][0] = inxs[findDsu(adds[e][0])] , adds[e][1] = inxs[findDsu(adds[e][1])];
        dts.pb({int(1e9) , adds[e][0] , adds[e][1]});
    }
    n = cnt , init();
}
int timer = -1;
void dfs1(int v = rt , int p = -1){
    ps[v] = p , tms[v][0] = ++timer;
    for(int e : g[v]){
        if(e == p) continue;
        int u = dts[e][1] + dts[e][2] - v;
        dfs1(u , e);
    }
    tms[v][1] = timer;
}
void setMn(int v1 , int v2 , int val){
    int u = v1;
    while(tms[u][0] > tms[v2][0] or tms[u][1] < tms[v2][0]){
        dts[ps[u]][0] = min(dts[ps[u]][0] , val);
        u = dts[ps[u]][1] + dts[ps[u]][2] - u;
    }
    u = v2;
    while(tms[u][0] > tms[v1][0] or tms[u][1] < tms[v1][0]){
        dts[ps[u]][0] = min(dts[ps[u]][0] , val);
        u = dts[ps[u]][1] + dts[ps[u]][2] - u;
    }
}
ll dfs2(int v = rt){
    ll res = 0;
    mem[v] = a[v];
    for(int e : g[v]){
        if(e == ps[v]) continue;
        int u = dts[e][1] + dts[e][2] - v;
        res += dfs2(u) , mem[v] += mem[u];
        res += (1ll * dts[e][0]) * mem[u];
    }
    return res;
}
ll getCst(int msk){
    ll res;
    for(int e = 0 ; e < k ; e++){
        if(!((msk >> e) & 1)) continue;
        int r1 = findDsu(adds[e][0]) , r2 = findDsu(adds[e][1]);
        if(r1 == r2){
            init();
            return 0;
        }
        uDsu(r1 , r2);
    }
    for(int e = 0 ; e < k ; e++){
        if(!((msk >> e) & 1)) continue;
        g[adds[e][0]].pb((int)cnds.size() + e) , g[adds[e][1]].pb((int)cnds.size() + e);
    }
    for(int e = 0 ; e < (int)cnds.size() ; e++){
        int r1 = findDsu(cnds[e][1]) , r2 = findDsu(cnds[e][2]);
        if(r1 != r2){
            uDsu(r1 , r2);
            g[cnds[e][1]].pb(e) , g[cnds[e][2]].pb(e);
        }
    }
    timer = -1 , dfs1();
    for(auto &e : cnds) setMn(e[1] , e[2] , e[0]);
    res = dfs2();
    for(int e = (int)cnds.size() ; e < (int)cnds.size() + k ; e++) dts[e][0] = int(1e9);
    for(int i = 0 ; i < n ; i++) g[i].cl();
    init();
    return res;
}
ll f(){
    ll res = 0;
    for(int msk = 1 ; msk < (1 << k) ; msk++){
        res = max(res , getCst(msk));
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    vector<arr(3)> es;
    for(int i = 0 ; i < m ; i++){
        int v , u , c;
        cin >> v >> u >> c;
        v-- , u--;
        es.pb({c , v , u});
    }
    for(int i = 0 ; i < k ; i++){
        int v , u;
        cin >> v >> u;
        adds.pb({v - 1 , u - 1});
    }
    for(int i = 0 ; i < n ; i++){
        int d;
        cin >> d;
        a.pb(d);
    }
    init();
    sort(es.bg() , es.end());
    for(auto e : es){
        if(findDsu(e[1]) == findDsu(e[2])) continue;
        mst.pb(e) , uDsu(e[1] , e[2]);
    }
    init() , getCnds();
    cout << f();
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 133 ms 10936 KB Output is correct
8 Correct 143 ms 10936 KB Output is correct
9 Correct 160 ms 10748 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 133 ms 10936 KB Output is correct
8 Correct 143 ms 10936 KB Output is correct
9 Correct 160 ms 10748 KB Output is correct
10 Correct 910 ms 11480 KB Output is correct
11 Correct 1439 ms 17704 KB Output is correct
12 Correct 1470 ms 18100 KB Output is correct