oj.uz

Submission #580916

# Submission time Handle Problem Language Result Execution time Memory
580916 2022-06-22T06:10:11 Z 박상훈(#8359) Toll (APIO13_toll) C++17
56 / 100
 2500 ms 13808 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[22];

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

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){
    if (!z) return 0;
    if (!valid_bit(z)) return 0;

    ///init
    dsu2.clear();
    ST.clear();
    for (int i=0;i<=k;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];
    }

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

    ///subtask 3
    dfs0(idx[1]);
    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);

    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:123:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:124:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     for (int i=1;i<=m;i++) scanf("%d %d %d", &a[i].s, &a[i].e, &a[i].x);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:125:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     for (int i=0;i<k;i++) scanf("%d %d", &b[i].s, &b[i].e);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:127:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     for (int i=1;i<=n;i++) scanf("%d", w+i);
      |                            ~~~~~^~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 4 ms 324 KB Output is correct
5 Correct 170 ms 480 KB Output is correct
6 Correct 133 ms 480 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 4 ms 324 KB Output is correct
5 Correct 170 ms 480 KB Output is correct
6 Correct 133 ms 480 KB Output is correct
7 Execution timed out 2542 ms 13808 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 4 ms 324 KB Output is correct
5 Correct 170 ms 480 KB Output is correct
6 Correct 133 ms 480 KB Output is correct
7 Execution timed out 2542 ms 13808 KB Time limit exceeded
8 Halted 0 ms 0 KB -