Submission #114449

#	Time	Username	Problem	Language	Result	Execution time	Memory
114449		popovicirobert	Islands (IOI08_islands)	C++14	27 / 100	2035 ms	116584 KiB

islands

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

vector < vector <int> > g;
vector <int> to, cst;
vector <bool> bad, vis;

vector <int> par, lvl, nodes;
vector <ll> dst;

int n;

inline int get(int id) {
    if(id > n) return id - n;
    return id + n;
}

inline int bfs(int nod, bool type) {
    queue <int> Q;
    Q.push(nod);

    vis[nod] = 1;
    dst[nod] = 0;

    int id;

    while(Q.size()) {
        nod = Q.front();
        Q.pop();

        if(type) {
            nodes.push_back(nod);
        }

        for(auto it : g[nod]) {
            if(vis[to[it]] == 0 && bad[it] == 0) {
                vis[to[it]] = 1;
                Q.push(to[it]);

                dst[to[it]] = dst[nod] + cst[it];
                bad[it] = bad[get(it)] = 1;

                if(type) {
                    par[to[it]] = get(it);
                    lvl[to[it]] = lvl[nod] + 1;
                }
            }
            else if(type && bad[it] == 0) {
                id = it;
            }
        }
    }

    return id;

}

inline ll solve(int nod) {

    nodes.clear();
    int e = bfs(nod, 1);

    ll mx = 0;
    int id;
    for(auto it : nodes) {
        vis[it] = 0;

        if(mx < dst[it]) {
            mx = dst[it];
            id = it;
        }

        for(auto itr : g[it]) {
            bad[itr] = 0;
        }
    }

    bfs(id, 0);

    ll ans = 0;
    for(auto it : nodes) {
        vis[it] = 0;

        ans = max(ans, dst[it]);

        for(auto itr : g[it]) {
            bad[itr] = 0;
        }
    }

    int a = to[get(e)], b = to[e];

    int mn = 1e9;

    while(a != b) {
        if(lvl[a] < lvl[b]) {
            swap(a, b);
        }

        if(cst[par[a]] < mn) {
            mn = cst[par[a]];
            e = par[a];
        }

        a = to[par[a]];
    }

    bad[e] = bad[get(e)] = 1;

    bfs(nod, 0);

    mx = 0;
    for(auto it : nodes) {
        vis[it] = 0;
        if(dst[it] > mx) {
            mx = dst[it];
            id = it;
        }

        for(auto itr : g[it]) {
            bad[itr] = 0;
        }
    }

    bad[e] = bad[get(e)] = 1;

    bfs(id, 0);

    for(auto it : nodes) {
        ans = max(ans, dst[it]);
    }

    return ans;

}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    g.resize(n + 1);
    to.resize(2 * n + 1), cst.resize(2 * n + 1);

    for(i = 1; i <= n; i++) {
        cin >> to[i] >> cst[i];
        g[i].push_back(i);

        to[i + n] = i, cst[i + n] = cst[i];
        g[to[i]].push_back(i + n);
    }

    vis.resize(n + 1), bad.resize(2 * n + 1);

    par.resize(n + 1), lvl.resize(n + 1);
    dst.resize(n + 1);

    ll ans = 0;
    for(i = 1; i <= n; i++) {
        if(vis[i] == 0) {
            ans += solve(i);
        }
    }

    cout << ans;

    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

islands.cpp: In function 'int main()':
islands.cpp:70:9: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int id;
         ^~
islands.cpp:20:5: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(id > n) return id - n;
     ^~
islands.cpp:31:9: note: 'id' was declared here
     int id;
         ^~

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