oj.uz

Submission #580912

# Submission time Handle Problem Language Result Execution time Memory
580912 2022-06-22T06:00:11 Z 박상훈(#8359) Toll (APIO13_toll) C++17
16 / 100
 1 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[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];
int idx[200200];
vector<pair<int, int>> adj[22];

ll solve(int z){
    if (!z) return 0;
    if (!valid_bit(z)) return 0;

    ///init
    dsu2.clear();
    for (int i=1;i<=k;i++){
        adj[i].clear();
        sw[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 1
    int val = 1e9;
    for (int i=1;i<=m;i++) if (idx[a[i].s]!=idx[a[i].e]){
        val = min(val, a[i].x);
    }
    for (int i=1;i<=2;i++) if (i!=idx[1]) return sw[i] * val;
    ///
    return 0;
}

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

    printf("%lld\n", solve(1));
    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:92:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     for (int i=1;i<=m;i++) scanf("%d %d %d", &a[i].s, &a[i].e, &a[i].x);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:93:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     for (int i=0;i<k;i++) scanf("%d %d", &b[i].s, &b[i].e);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:95:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 22.0

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