oj.uz

Submission #684170

# Submission time Handle Problem Language Result Execution time Memory
684170 2023-01-20T15:11:48 Z finn__ Railway (BOI17_railway) C++17
36 / 100
 123 ms 30404 KB 
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<unsigned, unsigned>>> g;
vector<vector<unsigned>> jmp;
vector<unsigned> height, pre, ans;
vector<int> val;

unsigned lift(unsigned u, unsigned h)
{
    unsigned z = 0;
    while (h)
    {
        if (h & 1)
            u = jmp[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 (size_t i = jmp[u].size() - 1; i < jmp[u].size(); i--)
        if (jmp[u][i] != jmp[v][i])
            u = jmp[u][i], v = jmp[v][i];

    return jmp[u][0];
}

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

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

    path.pop_back();
    return i;
}

void calc_ans(unsigned u, unsigned p)
{
    for (auto const &[v, j] : g[u])
    {
        if (v != p)
        {
            calc_ans(v, u);
            ans[j] = val[v];
            val[u] += val[v];
        }
    }
}

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

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

    g = vector<vector<pair<unsigned, unsigned>>>(n);
    jmp = vector<vector<unsigned>>(n);
    height = vector<unsigned>(n);
    pre = vector<unsigned>(n);
    ans = vector<unsigned>(n - 1);
    val = vector<int>(n, 0);

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

    vector<unsigned> path;
    traverse(path, 0, -1, 0, 0);

    for (size_t i = 0; i < m; i++)
    {
        size_t s;
        cin >> s;
        vector<pair<unsigned, unsigned>> y(s);
        for (auto &[j, u] : y)
        {
            cin >> u;
            u--;
            j = pre[u];
        }
        sort(y.begin(), y.end());

        for (size_t j = 0; j < s; j++)
        {
            val[y[j].second]++;
            val[y[(j + 1) % s].second]++;
            val[lca(y[j].second, y[(j + 1) % s].second)] -= 2;
        }
    }

    calc_ans(0, -1);

    unsigned c = 0;
    for (unsigned const &x : ans)
        c += (x >= 2 * k);
    cout << c << '\n';
    for (size_t i = 0; i < n - 1; i++)
        if (ans[i] >= 2 * k)
            cout << i + 1 << ' ';
    cout << '\n';
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 1748 KB Output is correct
3 Incorrect 5 ms 1728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 1748 KB Output is correct
3 Incorrect 5 ms 1728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 30140 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 113 ms 29892 KB Output is correct
4 Correct 113 ms 29696 KB Output is correct
5 Correct 103 ms 30144 KB Output is correct
6 Correct 89 ms 30404 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 23896 KB Output is correct
2 Correct 92 ms 20140 KB Output is correct
3 Correct 88 ms 15372 KB Output is correct
4 Correct 86 ms 15300 KB Output is correct
5 Correct 80 ms 15432 KB Output is correct
6 Correct 80 ms 24016 KB Output is correct
7 Correct 79 ms 23876 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 23896 KB Output is correct
2 Correct 92 ms 20140 KB Output is correct
3 Correct 88 ms 15372 KB Output is correct
4 Correct 86 ms 15300 KB Output is correct
5 Correct 80 ms 15432 KB Output is correct
6 Correct 80 ms 24016 KB Output is correct
7 Correct 79 ms 23876 KB Output is correct
8 Correct 88 ms 23928 KB Output is correct
9 Correct 92 ms 23980 KB Output is correct
10 Correct 98 ms 30100 KB Output is correct
11 Correct 88 ms 30148 KB Output is correct
12 Correct 50 ms 15016 KB Output is correct
13 Correct 54 ms 14920 KB Output is correct
14 Incorrect 82 ms 15180 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 1748 KB Output is correct
3 Incorrect 5 ms 1728 KB Output isn't correct
4 Halted 0 ms 0 KB -