Submission #1248072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248072		chuchucharles	Railway (BOI17_railway)	C++20	100 / 100	62 ms	23232 KiB

railway

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 1e15;

using namespace std;

int n, k, m, entry[100005], contain[100005], timedfs, up[20][100005], depth[100005], dp[100005];
vector<int> adj[100005];
pair<int, int> edge[100005];
void dfs(int now, int par)
{
    up[0][now] = par;
    entry[now] = ++timedfs;
    for (auto i : adj[now])
    {
        if (i == par)
            continue;
        depth[i] = depth[now] + 1;
        dfs(i, now);
    }
}

void build()
{
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= n; j++)
            up[i][j] = up[i - 1][up[i - 1][j]];
}

int kth(int x, int k)
{
    for (int i = 0; i < 20; i++)
        if ((k >> i) & 1)
            x = up[i][x];
    return x;
}

int lca(int l, int r)
{
    if (depth[l] > depth[r])
        swap(l, r);
    r = kth(r, depth[r] - depth[l]);
    if (l == r)
        return l;
    for (int i = 19; i >= 0; i--)
    {
        if (up[i][l] != up[i][r])
        {
            l = up[i][l];
            r = up[i][r];
        }
    }
    return up[0][l];
}

void dfs1(int now, int par)
{
    for (auto i : adj[now])
    {
        if (i == par)
            continue;
        dfs1(i, now);
        dp[now] += dp[i];
    }
}

bool cmp(int jack, int mck)
{
    return entry[jack] < entry[mck];
}

fami lore()
{
    // freopen("SUADUONG.inp", "r", stdin);
    // freopen("SUADUONG.out", "w", stdout);
    SPED;
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        adj[l].emplace_back(r);
        adj[r].emplace_back(l);
        edge[i] = {l, r};
    }
    dfs(1, 0);
    build();
    for (int i = 1; i < n; i++)
    {
        auto [u, v] = edge[i];
        if (depth[u] > depth[v])
            contain[u] = i;
        else
            contain[v] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        int a[x + 1];
        for (int j = 1; j <= x; j++)
        {
            cin >> a[j];
            ++dp[a[j]];
        }

        int niga = a[1];

        for (int i = 2; i <= x; i++)
            niga = lca(niga, a[i]);

        sort(a + 1, a + 1 + x, cmp);
        for (int i = 2; i <= x; i++)
            dp[lca(a[i - 1], a[i])] -= 1;
        dp[niga] -= 1;
    }
    dfs1(1, 0);
    vector<int> suggest;
    for (int i = 2; i <= n; i++)
        if (dp[i] >= k)
            suggest.emplace_back(contain[i]);
    sort(suggest.begin(), suggest.end());
    cout << suggest.size() << endl;
    for (auto z : suggest)
        cout << z << " ";
}
// Let your soul wander where dreams are born.

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