Submission #114666

#	Time	Username	Problem	Language	Result	Execution time	Memory
114666		zubec	Islands (IOI08_islands)	C++14	30 / 100	707 ms	131072 KiB

islands

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 1000100;

int dsu[N], sz[N];

int n;

int dsu_get(int v){
    if (dsu[v] == v)
        return v;
    return dsu[v] = dsu_get(dsu[v]);
}

void dsu_unite(int a, int b){
    a = dsu_get(a);
    b = dsu_get(b);
    if (a == b)
        return;
    if (sz[a] < sz[b])
        swap(a, b);
    sz[a] += sz[b];
    dsu[b] = a;
}

ll ans = 0;

vector <int> g[N];

int len[N], nxt[N];

vector <pair<int, int> > gg[N];

bool used[N];

ll mx = -1;
int mxver = 0;

void dfs(int v, int p, ll curlen){
    if (curlen > mx){
        mx = curlen;
        mxver = v;
    }
    for (int i = 0; i < gg[v].size(); i++){
        int to = gg[v][i].first, len = gg[v][i].second;
        if (to != p)
            dfs(to, v, curlen+len);
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++){
        dsu[i] = i;
        sz[i] = 1;
    }
    for (int i = 1; i <= n; i++){
        int to;
        cin >> to >> len[i];
        nxt[i] = to;
        g[i].push_back(to);
        g[to].push_back(i);
    }
    for (int i = 1; i <= n; i++){
        if (used[i])
            continue;
        queue <int> q;
        vector <pair<int, pair<int, int> > > vec;
        q.push(i);
        while(!q.empty()){
            int v = q.front();
            q.pop();
            vec.push_back({len[v], {v, nxt[v]}});
            for (int j = 0; j < g[v].size(); j++){
                int to = g[v][j];
                if (!used[to]){
                    used[to] = 1;
                    q.push(to);
                }
            }
        }
        sort(vec.rbegin(), vec.rend());
        for (int i = 0; i < vec.size(); i++){
            int a = vec[i].second.first, b = vec[i].second.second;
            if (dsu_get(a) != dsu_get(b)){
                gg[a].push_back({b, vec[i].first});
                gg[b].push_back({a, vec[i].first});
                dsu_unite(a, b);
            }
        }
        mx = -1, mxver = 0;
        dfs(i, 0, 0);
        mx = -1;
        dfs(mxver, 0, 0);
        ans += mx;
    }
    cout << ans;


}

Compilation message (stderr)

islands.cpp: In function 'void dfs(int, int, ll)':
islands.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < gg[v].size(); i++){
                     ~~^~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:79:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g[v].size(); j++){
                             ~~^~~~~~~~~~~~~
islands.cpp:88:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < vec.size(); i++){
                         ~~^~~~~~~~~~~~

• Subtask 1: 27 / 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