Submission #581204

#	Time	Username	Problem	Language	Result	Execution time	Memory
581204		qwerasdfzxcl	Toll (APIO13_toll)	C++14	100 / 100	2288 ms	19640 KiB

toll

#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, aaa[500500];
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;
}

int ST[44], stc;
bool dfs(int s, int e, int pa = -1){
    if (s==e) return 1;
    for (auto &[v, i]:adj[s]) if (v!=pa){
        ST[stc++] = i;
        if (dfs(v, e, s)) return 1;
        stc--;
    }
    return 0;
}

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

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

    for (int i=0;i<=n;i++) aaa[i] = -1;
    ///

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

    int aac = 1;
    for (int i=1;i<=n;i++) if (aaa[dsu2.find(i)]==-1) aaa[dsu2.find(i)] = aac++;



    for (int i=1;i<=n;i++){

        idx[i] = aaa[dsu2.find(i)];
        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 = aac-1;
        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 (x>y){
                swap(a[i].s, a[i].e);
                swap(x, y);
            }
            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]){
        stc = 0;
        assert(dfs(idx[a[i].s], idx[a[i].e]));

        for (int j=0;j<stc;j++) mn[ST[j]] = min(mn[ST[j]], a[i].x);
    }

    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;
}

Compilation message (stderr)

toll.cpp: In function 'll dfs0(long long int, long long int)':
toll.cpp:53:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for (auto &[v, i]:adj[s]) if (v!=pa){
      |                ^
toll.cpp: In function 'bool dfs(long long int, long long int, long long int)':
toll.cpp:64:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |     for (auto &[v, i]:adj[s]) if (v!=pa){
      |                ^

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22