oj.uz

답안 #432559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
432559 2021-06-18T11:04:03 Z tengiz05 Islands (IOI08_islands) C++17
0 / 100
 2000 ms 131076 KB 
#include <bits/stdc++.h>
using i64 = long long;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<std::set<std::pair<int, int>>> e(n), al(n);
    for (int i = 0; i < n; i++) {
        int to, cost;
        std::cin >> to >> cost;
        to--;
        e[i].emplace(to, cost);
        e[to].emplace(i, cost);
        al[i].emplace(to, cost);
        al[to].emplace(i, cost);
    }
    std::vector<bool> vis(n);
    int timer = 0;
    std::vector<int> in(n), low(n);
    std::vector<std::tuple<int, int, int>> br;
    std::function<void(int, int)> dfs = [&](int u, int p) {
        in[u] = low[u] = timer++;
        vis[u] = true;
        for (auto [v, w] : e[u]) {
            if (v == p) {
                continue;
            }
            if (vis[v]) {
                low[u] = std::min(low[u], in[v]);
            } else {
                dfs(v, u);
                low[u] = std::min(low[u], low[v]);
                if (low[v] > low[u]) {
                    // bridge u -> v
                    br.emplace_back(u, v, w);
                }
            }
        }
    };
    for (int i = 0; i < n; i++) {
        if (!vis[i]) 
            dfs(0, -1);
    }
    for (auto [x, y, z] : br) {
        al[x].erase(al[x].lower_bound({y, z}));
        al[y].erase(al[y].lower_bound({x, z}));
    }
    std::vector<i64> v{0}, pos(n, 0), comp(n), sum(n);
    std::iota(pos.begin(), pos.end(), 0);
    std::vector<std::vector<int>> contain;
    vis.assign(n, false);    timer = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i]) {
            continue;
        }
        comp[i] = timer;
        pos[i] = v.size();
        v.push_back(v.back());
        contain.push_back({});
        if (al[i].size()) {
            int u = i;
            contain[timer].push_back(u);
            vis[u] = true;
            while (!vis[al[u].begin()->first] || !vis[(++al[u].begin())->first]) {
                i64 cost;
                if (vis[al[u].begin()->first]) {
                    u = (++al[u].begin())->first;
                    cost = (++al[u].begin())->second;
                } else {
                    u = al[u].begin()->first;
                    cost = al[u].begin()->second;
                }
                contain[timer].push_back(u);
                vis[u] = true;
                comp[u] = timer;
                pos[u] = v.size();
                sum[timer] += cost;
                v.push_back(v.back() + cost);
            }
                if (vis[al[u].begin()->first]) {
                    sum[timer] += (++al[u].begin())->second;
                } else {
                    sum[timer] += al[u].begin()->second;
                }
        }
        timer++;
    }
    // std::cerr << "what the fuck\n";
    // for (int i = 0; i < n; i++) {
    //     std::cout << comp[i] << " \n"[i == n - 1];
    // }
    for (int i = 0; i < n; i++) {
        e[i].clear();
    }
    for (auto [x, y, z] : br) {
        e[x].insert({y, z});
        e[y].insert({x, z});
    }
    i64 ans = 0;
    std::vector<i64> f(n);
    for (int i = 0; i < timer; i++) {
        i64 res = 0;
        std::function<i64(int, int)> dfs2 = [&](int u, int p) -> i64 {
            i64 mx = 0;
            for (auto [v, w] : e[u]) {
                if (v != p) {
                    mx = std::max(mx, dfs2(v, u) + w);
                }
            }
            return mx;
        };
        for (auto u : contain[i]) {
            f[u] = dfs2(u, -1);
        }
        for (auto U : contain[i]) {
            for (auto V : contain[i]) {
                if (U == V) continue;
                assert(comp[U] == comp[V]);
                if (pos[U] > pos[V]) std::swap(U, V);
                if (U == 1 && V == 6) {
                    // std::cout << "YES ";
                    // std::cout << sum[comp[U]] << " " << v[pos[V]] - v[pos[U] - 1] << "\n";
                }
                res = std::max(res, f[U] + f[V] + std::max(v[pos[V]] - v[pos[U] - 1], sum[comp[U]] - (v[pos[V]] - v[pos[U] - 1])));
            }
        }
        ans += res;
        // std::cout << ans << "\n";
    }
    std::cout << ans << "\n";
    return 0;
}

Subtask #1
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Incorrect 2 ms 476 KB Output isn't correct
4 Incorrect 1 ms 304 KB Output isn't correct
5 Incorrect 0 ms 204 KB Output isn't correct
6 Incorrect 0 ms 316 KB Output isn't correct
7 Incorrect 1 ms 252 KB Output isn't correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Execution timed out 2086 ms 332 KB Time limit exceeded
11 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2077 ms 5332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2029 ms 21656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2064 ms 81592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2062 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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