oj.uz

답안 #685654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685654 2023-01-24T18:34:21 Z finn__ Training (IOI07_training) C++17
0 / 100
 1 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    unsigned u, v, w;
};

vector<vector<unsigned>> g, anc;
vector<unsigned> height, ind;
vector<vector<Edge>> unpaved;
vector<vector<unsigned>> dp;

unsigned lift(unsigned u, unsigned h)
{
    unsigned z = 0;
    while (h)
    {
        if (h & 1)
            u = anc[u][z];
        h >>= 1;
        z++;
    }
    return u;
}

unsigned lca(unsigned u, unsigned v)
{
    if (height[u] < height[v])
        swap(u, v);
    u = lift(u, height[u] - height[v]);
    if (u == v)
        return u;

    for (unsigned i = anc[u].size() - 1; i < anc[u].size(); i--)
    {
        if (anc[u][i] != anc[v][i])
        {
            u = anc[u][i];
            v = anc[v][i];
        }
    }

    return anc[u][0];
}

void traverse(unsigned u, vector<unsigned> &path, unsigned p = -1, unsigned h = 0)
{
    for (unsigned i = 1; i <= path.size(); i <<= 1)
        anc[u].push_back(path[path.size() - i]);
    height[u] = h;
    path.push_back(u);

    for (unsigned const &v : g[u])
        if (v != p)
            traverse(v, path, u, h + 1);

    for (auto it = g[u].begin(); it != g[u].end(); it++)
    {
        if (*it == p)
        {
            g[u].erase(it);
            break;
        }
    }

    path.pop_back();
}

void calc_dp(unsigned u)
{
    for (unsigned const &v : g[u])
    {
        calc_dp(v);
    }

    dp[u] = vector<unsigned>(1 << g[u].size());
    // Case 1. Just delete the root and add up subtree values.
    for (unsigned z = 0; z < 1U << g[u].size(); z++)
    {
        dp[u][z] = 0;
        for (unsigned i = 0; i < g[u].size(); i++)
        {
            if (!(z & (1 << i)))
            {
                dp[u][z] += dp[g[u][i]][0];
            }
        }
    }

    for (unsigned i = 0; i < g[u].size(); i++)
    {
        ind[g[u][i]] = i;
    }

    // Case 2: Take exactly one unpaved road whose tree path contains u.
    for (auto const &[a, b, w] : unpaved[u])
    {
        // Stores just the value obtained from the two used subtrees.
        unsigned x = 0;
        if (a != u)
        {
            x += dp[a][0];
            unsigned r = a, s = anc[a][0];
            while (s != u)
            {
                x += dp[s][1 << ind[r]];
                r = s;
                s = anc[s][0];
            }
        }
        if (b != u)
        {
            x += dp[b][0];
            unsigned r = b, s = anc[b][0];
            while (s != u)
            {
                x += dp[s][1 << ind[r]];
                r = s;
                s = anc[s][0];
            }
        }

        unsigned p = UINT_MAX, q = UINT_MAX;

        if (a != u)
            p = ind[lift(a, height[a] - height[u] - 1)];
        if (b != u)
            q = ind[lift(b, height[b] - height[u] - 1)];

        for (unsigned z = 0; z < 1U << g[u].size(); z++)
        {
            if ((a != u && (z & (1 << p))) || (b != u && (z & (1 << q))))
                continue;

            unsigned y = 0;
            // Sum all children not on an edge path and not ruled out.
            for (unsigned i = 0; i < g[u].size(); i++)
            {
                if (!(z & (1 << i)) && i != p && i != q)
                {
                    y += dp[g[u][i]][0];
                }
            }
            dp[u][z] = max(dp[u][z], x + y + w);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m;
    cin >> n >> m;

    assert(n > 10000);

    g = vector<vector<unsigned>>(n);
    vector<Edge> unpaved_edges;
    unsigned total_cost = 0;

    for (size_t i = 0; i < m; i++)
    {
        unsigned u, v, w;
        cin >> u >> v >> w;
        total_cost += w;

        if (!w)
        {
            g[u - 1].push_back(v - 1);
            g[v - 1].push_back(u - 1);
        }
        else
        {
            unpaved_edges.push_back({u - 1, v - 1, w});
        }
    }

    height = vector<unsigned>(n);
    anc = vector<vector<unsigned>>(n);
    vector<unsigned> path;
    traverse(0, path);

    unpaved = vector<vector<Edge>>(n);
    for (auto const &[u, v, w] : unpaved_edges)
    {
        if (!((height[u] + height[v]) & 1))
        {
            unpaved[lca(u, v)].push_back({u, v, w});
        }
    }

    dp = vector<vector<unsigned>>(n);
    ind = vector<unsigned>(n);
    calc_dp(0);

    cout << total_cost - dp[0][0] << '\n';
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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