Submission #1233547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233547		chikien2009	Railway (BOI17_railway)	C++20	29 / 100	1096 ms	19648 KiB

railway

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m, k, a, b;
int head[100000], tail[100000], pre[20][100000], val[100000], q[100000], lca[100000];
vector<pair<int, int>> g[100000];
vector<int> res;

inline void DFS(int node, int par)
{
    head[node] = a++;
    pre[0][node] = par;
    for (int i = 1; i < 20; ++i)
    {
        pre[i][node] = pre[i - 1][pre[i - 1][node]];
    }
    for (auto &i : g[node])
    {
        if (i.first != par)
        {
            DFS(i.first, node);
        }
    }
    tail[node] = a - 1;
}

inline void DFS1(int node, int par, int last)
{
    for (auto & i : g[node])
    {
        if (i.first != par)
        {
            DFS1(i.first, node, i.second);
            val[node] += val[i.first];
        }
    }
    // cout << node << " " << val[node] << "\n";
    if (val[node] >= k)
    {
        res.push_back(last);
    }
}

inline bool comp(const int &ina, const int &inb)
{
    return head[a] < head[b];
}

inline bool IsPar(int par, int child)
{
    return head[par] <= head[child] && tail[child] <= tail[par];
}

inline int LCA(int ina, int inb)
{
    if (IsPar(ina, inb))
    {
        return ina;
    }
    for (int i = 19; i >= 0; --i)
    {
        if (!IsPar(pre[i][ina], inb))
        {
            ina = pre[i][ina];
        }
    }
    return pre[0][ina];
}

int main()
{
    setup();

    cin >> n >> m >> k;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back({b - 1, i + 1});
        g[b - 1].push_back({a - 1, i + 1});
    }
    a = 0;
    DFS(0, 0);
    while (m--)
    {
        cin >> a;
        if (a <= 1)
        {
            continue;
        }
        for (int i = 0; i < a; ++i)
        {
            cin >> q[i];
            val[--q[i]]++;
        }
        sort(q, q + a, comp);
        lca[0] = pre[0][q[0]];
        val[lca[0]]--;
        for (int i = 1; i < a; ++i)
        {
            lca[i] = LCA(q[i - 1], q[i]);
            val[lca[i]] -= 2;
            val[lca[i - 1]] += 1;
        }
    }
    DFS1(0, 0, 0);
    sort(res.begin(), res.end());
    cout << res.size() << "\n";
    for (auto & i : res)
    {
        cout << i << " ";
    }
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 29 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25