oj.uz

Submission #114449

# Submission time Handle Problem Language Result Execution time Memory
114449 2019-06-01T11:30:47 Z popovicirobert Islands (IOI08_islands) C++14
27 / 100
 2000 ms 116584 KB 
#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

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.0 / 33.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5732 KB Output is correct
2 Incorrect 60 ms 10588 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 21604 KB Output is correct
2 Correct 151 ms 23156 KB Output is correct
3 Incorrect 155 ms 26800 KB Output isn't correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 116584 KB Output is correct
2 Execution timed out 2035 ms 107188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 106660 KB Output is correct
2 Correct 565 ms 106700 KB Output is correct
3 Correct 552 ms 106744 KB Output is correct
4 Correct 647 ms 101880 KB Output is correct
5 Correct 540 ms 104680 KB Output is correct
6 Incorrect 733 ms 102264 KB Output isn't correct
7 Halted 0 ms 0 KB -