oj.uz

Submission #581101

# Submission time Handle Problem Language Result Execution time Memory
581101 2022-06-22T09:13:43 Z 박상훈(#8359) Toll (APIO13_toll) C++17
0 / 100
 0 ms 212 KB 
#include <bits/stdc++.h>

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[300300], b[32], aa[32][32];

struct DSU{
    int path[100100];
    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[100100];

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[32], P[32];
int idx[200200], mn[32], ns;
vector<pair<int, int>> adj[32];

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;
        idx[i] = 0;
    }
    ///

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

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

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for (int i=1;i<=m;i++) scanf("%d %d %d", &a[i].s, &a[i].e, &a[i].x);
    for (int i=0;i<k;i++) scanf("%d %d", &b[i].s, &b[i].e);
    sort(a+1, a+m+1);
    for (int i=1;i<=n;i++) scanf("%d", w+i);

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

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

    //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

toll.cpp: In function 'int main()':
toll.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:158:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |     for (int i=1;i<=m;i++) scanf("%d %d %d", &a[i].s, &a[i].e, &a[i].x);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:159:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |     for (int i=0;i<k;i++) scanf("%d %d", &b[i].s, &b[i].e);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:161:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |     for (int i=1;i<=n;i++) scanf("%d", w+i);
      |                            ~~~~~^~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -