oj.uz

Submission #581127

# Submission time Handle Problem Language Result Execution time Memory
581127 2022-06-22T09:26:13 Z 박상훈(#8359) Toll (APIO13_toll) C++17
78 / 100
 2500 ms 13016 KB 
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

typedef long long ll;
using namespace std;
struct Edge{
    int s, e, x;
    Edge(){}
    Edge(int _s, int _e, int _x): s(_s), e(_e), x(_x) {}
    bool operator<(const Edge &E) const{
        return x < E.x;
    }
}a[500500], b[44], aa[44][44];

struct DSU{
    int path[500500];
    vector<int> st;

    void init(int n){for (int i=1;i<=n;i++) path[i] = i;}
    void clear(){for (auto &x:st) path[x] = x; st.clear();}

    int find(int s){
        if (s==path[s]) return s;
        return path[s] = find(path[s]);
    }
    bool merge(int s, int v){
        s = find(s), v = find(v);
        if (s==v) return 0;
        path[s] = v;
        st.push_back(s);
        return 1;
    }
}dsu1, dsu2;

int n, m, k, w[500500];

bool valid_bit(int z){
    dsu1.clear();
    for (int i=0;i<k;i++) if (z&(1<<i)){
        if (!dsu1.merge(b[i].s, b[i].e)) return 0;
    }
    return 1;
}

ll sw[44], P[44];
int idx[500500], mn[44], ns;
vector<pair<int, int>> adj[44];

ll dfs0(int s, int pa = -1){
    ll ret = sw[s];
    for (auto &[v, i]:adj[s]) if (v!=pa){
        ll tmp = dfs0(v, s);
        ret += tmp;
        P[i] = tmp;
    }
    return ret;
}

vector<int> ST;
bool dfs(int s, int e, int pa = -1){
    if (s==e) return 1;
    for (auto &[v, i]:adj[s]) if (v!=pa){
        ST.push_back(i);
        if (dfs(v, e, s)) return 1;
        ST.pop_back();
    }
    return 0;
}

ll solve(int z, bool flag = 0){
    if (!z) return 0;
    if (!valid_bit(z)){
        if (!flag) return 0;
    }

    ///init
    dsu2.clear();
    ST.clear();
    for (int i=0;i<=k+10;i++){
        adj[i].clear();
        sw[i] = 0;
        P[i] = 0;
        mn[i] = 1e9;
    }
    ///

    for (int i=1;i<=m;i++) if (dsu1.merge(a[i].s, a[i].e)){
        dsu2.merge(a[i].s, a[i].e);
    }

    vector<int> V;
    for (int i=1;i<=n;i++) V.push_back(dsu2.find(i));
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());


    for (int i=1;i<=n;i++){
        idx[i] = lower_bound(V.begin(), V.end(), dsu2.find(i)) - V.begin() + 1;
        sw[idx[i]] += w[i];
        //printf(" YES %d %d\n", i, w[i]);
    }

    for (int i=0;i<k;i++) if (z&(1<<i)){
        adj[idx[b[i].s]].emplace_back(idx[b[i].e], i);
        adj[idx[b[i].e]].emplace_back(idx[b[i].s], i);
    }


    ///new graph

    if (flag){
        int nc = V.size();
        ns = idx[1];

        for (int i=1;i<=m;i++) if (idx[a[i].s]!=idx[a[i].e]){
            int x = idx[a[i].s], y = idx[a[i].e];
            if (aa[x][y].x) aa[x][y] = min(aa[x][y], Edge(idx[a[i].s], idx[a[i].e], a[i].x));
            else aa[x][y] = Edge(idx[a[i].s], idx[a[i].e], a[i].x);
        }

        int ncnt = 1;
        for (int i=1;i<=nc;i++){
            for (int j=1;j<=nc;j++) if (aa[i][j].x) a[ncnt++] = aa[i][j];
        }
        for (int i=0;i<k;i++){
            b[i].s = idx[b[i].s];
            b[i].e = idx[b[i].e];
        }

        m = ncnt-1;
        n = nc;
        for (int i=1;i<=n;i++) w[i] = sw[i];

        sort(a+1, a+m+1);
        vector<Edge> tmptmp;
        dsu1.clear();
        for (int i=1;i<=m;i++) if (dsu1.merge(a[i].s, a[i].e)) tmptmp.push_back(a[i]);
        for (int i=0;i<(int)tmptmp.size();i++) a[i+1] = tmptmp[i];

        m = tmptmp.size();

        return 0;

    }


    ///subtask 3
    dfs0(idx[ns]);
    for (int i=1;i<=m;i++) if (idx[a[i].s]!=idx[a[i].e]){
        assert(dfs(idx[a[i].s], idx[a[i].e]));
        for (auto &j:ST) mn[j] = min(mn[j], a[i].x);
        ST.clear();
    }

    ll ret = 0;
    for (int i=0;i<k;i++) if (z&(1<<i)){
        ret += P[i] * mn[i];
        //printf("%lld %d\n", P[i], mn[i]);
    }

    return ret;
}

signed main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> k;
    for (int i=1;i<=m;i++) cin >> a[i].s >> a[i].e >> a[i].x;
    for (int i=0;i<k;i++) cin >> b[i].s >> b[i].e;
    sort(a+1, a+m+1);
    for (int i=1;i<=n;i++) cin >> w[i];

    dsu1.init(n); dsu2.init(n);

    solve((1<<k)-1, 1);

    assert(m<=30);

    //printf(" %d %d %d %d\n", n, m, k, ns);
    //for (int i=1;i<=m;i++) printf(" %d %d %d\n", a[i].s, a[i].e, a[i].x);
    //for (int i=1;i<=n;i++) printf(" %d ", w[i]);
    //printf("\n");

    ll ans = 0;
    for (int z=1;z<(1<<k);z++) ans = max(ans, solve(z));
    printf("%lld\n", ans);
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 340 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 207 ms 12944 KB Output is correct
8 Correct 234 ms 12980 KB Output is correct
9 Correct 209 ms 12956 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 207 ms 12944 KB Output is correct
8 Correct 234 ms 12980 KB Output is correct
9 Correct 209 ms 12956 KB Output is correct
10 Correct 2149 ms 13016 KB Output is correct
11 Execution timed out 2557 ms 12936 KB Time limit exceeded
12 Halted 0 ms 0 KB -