oj.uz

Submission #687531

# Submission time Handle Problem Language Result Execution time Memory
687531 2023-01-26T13:40:22 Z finn__ Islands (IOI08_islands) C++17
12 / 100
 920 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

vector<map<unsigned, unsigned>> g;

bool find_cycle(unsigned u, vector<unsigned> &c, vector<bool> &vis, unsigned p = -1)
{
    if (vis[u])
        return 1;

    vis[u] = 1;
    for (auto const &[v, w] : g[u])
        if (v != p)
            if (find_cycle(v, c, vis, u))
            {
                c.push_back(u);
                return 1;
            }

    return 0;
}

// Returns (longest path inside subtree, longest path to root)
pair<uint64_t, uint64_t> longest_tree_path(unsigned u, unsigned p = -1)
{
    pair<uint64_t, uint64_t> ans = {0, 0};
    for (auto const &[v, w] : g[u])
    {
        if (v != p)
        {
            auto const [sl, rl] = longest_tree_path(v, u);
            ans.first = max(ans.first, max(sl, ans.second + rl + w));
            ans.second = max(ans.second, rl + w);
        }
    }
    return ans;
}

uint64_t longest_simple_path(unsigned u, vector<bool> &cvis)
{
    vector<unsigned> c;
    find_cycle(u, c, cvis);

    if (c.empty())
        return longest_tree_path(u).first;

    size_t const m = c.size();
    vector<uint64_t> root_paths(c.size());
    uint64_t ans = 0;
    vector<unsigned> pre_dis(c.size()), next_dis(c.size());

    for (size_t i = 0; i < m; i++)
    {
        next_dis[i] = g[c[i]][c[(i + 1) % m]];
        pre_dis[i] = g[c[i]][c[(i - 1 + m) % m]];
        g[c[i]].erase(c[(i + 1) % m]);
        g[c[i]].erase(c[(i - 1 + m) % m]);

        auto const [sl, rl] = longest_tree_path(c[i]);
        ans = max(ans, sl);
        root_paths[i] = rl;
    }

    int64_t dp = 0, prefix_sum = 0;
    for (size_t i = 0; i < m; i++)
    {
        ans = max(ans, root_paths[i] + prefix_sum + dp);
        dp = max(dp, (int64_t)root_paths[i] - (int64_t)prefix_sum);
        prefix_sum += next_dis[i];
    }

    reverse(c.begin(), c.end());
    reverse(root_paths.begin(), root_paths.end());
    reverse(pre_dis.begin(), pre_dis.end());
    dp = 0, prefix_sum = 0;

    for (size_t i = 0; i < m; i++)
    {
        ans = max(ans, root_paths[i] + prefix_sum + dp);
        dp = max(dp, (int64_t)root_paths[i] - (int64_t)prefix_sum);
        prefix_sum += pre_dis[i];
    }

    return ans;
}

void mark_component(unsigned u, vector<bool> &vis)
{
    vis[u] = 1;
    for (auto const &[v, w] : g[u])
        if (!vis[v])
            mark_component(v, vis);
}

int main()
{
    size_t n;
    cin >> n;

    g = vector<map<unsigned, unsigned>>(n);
    for (size_t i = 0; i < n; i++)
    {
        unsigned u, w;
        cin >> u >> w;
        g[i][u - 1] = max(g[i][u - 1], w);
        g[u - 1][i] = max(g[u - 1][i], w);
    }

    vector<bool> vis(n, 0), cvis(n, 0);
    uint64_t max_distance = 0;
    for (unsigned i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            mark_component(i, vis);
            max_distance += longest_simple_path(i, cvis);
        }
    }

    cout << max_distance << '\n';
}

Subtask #1
12.0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 304 KB Output isn't correct
2 Runtime error 141 ms 131072 KB Execution killed with signal 9
3 Incorrect 1 ms 304 KB Output isn't correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 292 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Runtime error 118 ms 131072 KB Execution killed with signal 9
9 Incorrect 0 ms 340 KB Output isn't correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 403 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 210 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 592 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 920 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 695 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -