Submission #1131299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131299		omar1312	Islands (IOI08_islands)	C++20	33 / 100	929 ms	196608 KiB

islands

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const int mod = 1000000007;
const int N = 1000001;
ll a[N+2], dp[N+2], cost[N+2];
bool vis[N+2];
struct Dsu{
    vector<ll> par, rank;
    Dsu(ll n) : par(n), rank(n){
        for(int i = 0; i < n; i++){
            par[i] = i;
        }
    }
    int find(int u){
        if(u == par[u])return u;
        return par[u] = find(par[u]);
    }
    void merge(int u, int v){
        u = find(u), v = find(v);
        if(u == v)return;
        if(rank[u] < rank[v])swap(u, v);
        rank[u] += (rank[u] == rank[v]);
        par[v] = u;
    }
};
vector<array<ll, 2>> adj[N+2];
vector<ll> order;
void dfs(int n){
    vis[n] = 1;
    // cout<<n<<' '<<cost[n]<<'\n';
    order.pb(n);
    for(auto [i, w] : adj[n]){
        if(!vis[i]){
            cost[i] = cost[n] + w;
            dfs(i);
        }
    }
}
void solve(){
    int n;
    cin>>n;
    vector<array<ll, 3>> v;
    for(int i = 0; i < n; i++){
        ll u, k;
        cin>>u>>k;
        --u;
        v.pb({k, u, i});
    }
    sort(all(v), greater<>());
    Dsu dsu(n);
    ll ans = 0;
    for(int i = 0; i < n; i++){
        if(dsu.find(v[i][1]) != dsu.find(v[i][2])){
            dsu.merge(v[i][1], v[i][2]);
            // cout<<"Added edge -> "<<v[i][1]<<' '<<v[i][2]<<'\n'<<"With cost -> "<<v[i][0]<<'\n';
            adj[v[i][1]].pb({v[i][2], v[i][0]});
            adj[v[i][2]].pb({v[i][1], v[i][0]});
        }
    }
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            // cout<<i<<'\n';
            dfs(i);
            array<ll, 2> mx = {0, 0};
            for(auto j : order){
                if(cost[j] > mx[0]){
                    mx[0] = cost[j];
                    mx[1] = j;
                }
                vis[j] = 0;
                cost[j] = 0;
            }
            order.clear();
            // cout<<'\n';
            dfs(mx[1]);
            mx = {0, 0};
            for(auto j : order){
                if(cost[j] > mx[0]){
                    mx[0] = cost[j];
                    mx[1] = j;
                }
            }
            // cout<<mx[0]<<'\n';
            ans += mx[0];
            order.clear();
        }
    }
    cout<<ans;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    //cin>>tt;
    while(tt--){
        solve();
        cout<<'\n';
    }
}

• 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