oj.uz

답안 #687657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
687657 2023-01-26T18:16:47 Z finn__ Islands (IOI08_islands) C++17
90 / 100
 1508 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<unsigned, unsigned>>> g;

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

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

    return {0, UINT_MAX};
}

// Returns (longest path inside subtree, longest path to root)
pair<int64_t, int64_t> longest_tree_path(unsigned u, unsigned p = -1)
{
    pair<int64_t, int64_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;
}

int64_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<int64_t> root_paths(c.size());
    int64_t ans = 0;
    vector<unsigned> pre_dis(c.size()), next_dis(c.size());
    int64_t sum = 0;

    for (size_t i = 0; i < m; i++)
    {
        auto it = lower_bound(g[c[i]].begin(), g[c[i]].end(), make_pair(c[(i + 1) % m], 0U));
        assert(it != g[c[i]].end());
        next_dis[i] = it->second;
        sum += it->second;
        g[c[i]].erase(it);

        auto jt = lower_bound(g[c[i]].begin(), g[c[i]].end(), make_pair(c[(i - 1 + m) % m], 0U));
        assert(jt != g[c[i]].end());
        pre_dis[i] = jt->second;
        g[c[i]].erase(jt);
    }

    for (size_t i = 0; i < m; i++)
    {
        auto const [sl, rl] = longest_tree_path(c[i]);
        ans = max(ans, sl);
        root_paths[i] = rl;
    }

    int64_t dp1 = 0, dp2 = 0, prefix_sum = 0;
    for (size_t i = 0; i < m; i++)
    {
        if (i)
        {
            ans = max(ans, root_paths[i] + prefix_sum + dp1);
            ans = max(ans, sum + root_paths[i] - prefix_sum + dp2);
        }
        dp1 = max(dp1, root_paths[i] - prefix_sum);
        dp2 = max(dp2, root_paths[i] + prefix_sum);
        prefix_sum += next_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);
}

bool edge_cmp(pair<unsigned, unsigned> const &a, pair<unsigned, unsigned> const &b)
{
    return a.first == b.first;
}

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

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

    for (unsigned i = 0; i < n; i++)
    {
        sort(g[i].begin(), g[i].end(), greater<pair<unsigned, unsigned>>());
        g[i].resize(unique(g[i].begin(), g[i].end(), edge_cmp) - g[i].begin());
        sort(g[i].begin(), g[i].end());
    }

    vector<bool> vis(n, 0), cvis(n, 0);
    int64_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
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 724 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1516 KB Output is correct
2 Correct 26 ms 4300 KB Output is correct
3 Correct 17 ms 1876 KB Output is correct
4 Correct 8 ms 1052 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 5896 KB Output is correct
2 Correct 68 ms 9260 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 16076 KB Output is correct
2 Correct 151 ms 22852 KB Output is correct
3 Correct 198 ms 34064 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 286 ms 30852 KB Output is correct
2 Correct 339 ms 56360 KB Output is correct
3 Correct 373 ms 64432 KB Output is correct
4 Correct 487 ms 86880 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 715 ms 64304 KB Output is correct
2 Correct 1098 ms 111932 KB Output is correct
3 Correct 538 ms 60940 KB Output is correct
4 Correct 679 ms 103316 KB Output is correct
5 Correct 677 ms 103612 KB Output is correct
6 Correct 1508 ms 73168 KB Output is correct
7 Correct 756 ms 131072 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 755 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -