oj.uz

Submission #467732

# Submission time Handle Problem Language Result Execution time Memory
467732 2021-08-24T08:26:26 Z Karliver Islands (IOI08_islands) C++14
33 / 100
 1012 ms 131076 KB 
    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}
struct UNION_FIND {
    vector<int>parent;
    vector<int>sz;

    void init(int n) {
        parent.resize(n + 1);
        sz.resize(n + 1);

        for(int i = 0;i <= n;++i) {
            parent[i] = i;
            sz[i] = 1;

        }
    }



    int find_set(int v)  {
        if(v == parent[v]) {
            return v;
        }
        return parent[v] = find_set(parent[v]);
    }
    void unite(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if(a != b) {
            if(sz[a] < sz[b]) {
                swap(a, b);
            }
            parent[b] = a;
            sz[a] += sz[b];
        }
    }



};

struct edge {
    int e, d, w;
    bool operator<(const edge &c) {
        return w < c.w;
    }
};

void solve() {


    int n;
    cin >> n;

    V<ll> d1(n), d2(n);
    VV<pairs> g(n);
    V<edge> P;
    UNION_FIND U;
    U.init(n);
    forn(i, n) {
        int a, b;
        cin >> a >> b;
        --a;
        P.push_back({i, a, b});
    }

    sort(all(P));
    reverse(all(P));
    for(auto [f, s, w] : P) {
        if(U.find_set(f) != U.find_set(s)) {
            U.unite(f, s);
            g[f].emplace_back(s, w);
            g[s].emplace_back(f, w);
        }
    }

    V<int> st;

    V<bool> vis(n, false);
    V<ll> dis(n, 0);
    function<void(int, int)> dfs = [&](int v, int p) {
        st.push_back(v);
        vis[v] = 1;
        for(auto [c, w] : g[v]) {
            if(c == p)continue;
            dfs(c, v);
            ll x = d1[c] + w;
            if(d1[v] < x) {
                swap(d1[v], d2[v]);
                d1[v] = x;
            }
            else if(d2[v] < x)
                d2[v] = x;
        }
    };

    ll ret = 0;

    forn(i, n) {
        if(vis[i])continue;
        st.clear();
        dfs(i, -1);
        ll ps = 0;
        for(auto c : st)
            ckma(ps, d1[c] + d2[c]);

        ret += ps;
    }

    cout << ret << '\n';
}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Compilation message

islands.cpp: In function 'void solve()':
islands.cpp:95:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |     for(auto [f, s, w] : P) {
      |              ^
islands.cpp: In lambda function:
islands.cpp:110:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |         for(auto [c, w] : g[v]) {
      |                  ^

Subtask #1
30.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Incorrect 0 ms 204 KB Output isn't correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8664 KB Output is correct
2 Incorrect 67 ms 13400 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 26944 KB Output is correct
2 Correct 121 ms 32536 KB Output is correct
3 Incorrect 214 ms 42416 KB Output isn't correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 129776 KB Output is correct
2 Runtime error 1012 ms 131076 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 862 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -