제출 #467732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467732		Karliver	Islands (IOI08_islands)	C++14	33 / 100	1012 ms	131076 KiB

islands

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

}

컴파일 시 표준 에러 (stderr) 메시지

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 / 33
• Subtask 2: 3 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10