Submission #1096418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096418		Wewoo	Railway (BOI17_railway)	C++17	100 / 100	54 ms	27600 KiB

railway

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int MAXN = 1e5 + 105;
typedef pair <int, int> ii;
int log2(int n)
{
    return 32 - (int) __builtin_clz(n) - 1;
}

int n, m, k;
int u, v;
vector <ii> g[MAXN + 5];

int in[MAXN + 5], out[MAXN + 5], depth[MAXN + 5], Dad[MAXN + 5][20];
void DFS(int u, int pre)
{
    in[u] = ++out[0];
    for (ii E : g[u])
    {
        int v = E.S;
        if (v == pre) continue;

        depth[v] = depth[u] + 1;
        Dad[v][0] = u;

        DFS(v, u);
    }

    out[u] = out[0];
}

void initDad(int n)
{
    int N = log2(n);
    for (int j = 1; j <= N; ++j)
        for (int i = 1; i <= n; ++i)
            Dad[i][j] = Dad[Dad[i][j - 1]][j - 1];
}

bool upper(int v, int u)
{
    return (in[u] <= in[v] && out[v] <= out[u]);
}

int LCA(int u, int v)
{
    if (depth[u] > depth[v]) swap(u, v);
    if (upper(v, u)) return u;

    for (int i = log2(depth[u]); i >= 0; --i)
    {
        int Daddy = Dad[u][i];
        if (!upper(v, Daddy)) u = Daddy;
    }

    return Dad[u][0];
}

int cnt[MAXN + 5];
vector <ii> a;
stack <int> st;
vector <int> res;
void DFS_calc(int u, int pre)
{
    for (ii E : g[u])
    {
        int id = E.F;
        int v = E.S;

        if (v == pre) continue;
        DFS_calc(v, u);
        if (cnt[v] >= k) res.push_back(id);
        cnt[u] += cnt[v];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  
    cin >> n >> m >> k;
    for (int i = 1; i <= n - 1; ++i)
    {
        cin >> u >> v;
        g[u].push_back(ii(i, v));
        g[v].push_back(ii(i, u));
    }

    DFS(1, 1);
    initDad(n);

    while (m --)
    {
        int x;
        cin >> x;
        for (int i = 1; i <= x; ++i)
        {
            cin >> u;
            a.push_back(ii(in[u], u));
        }

        sort(a.begin(), a.end());

        int curLCA = a[0].S;
        for (int i = 1; i < x; ++i)
        {
            int u = a[i - 1].S, v = a[i].S;
            int lca = LCA(u, v);
            ++ cnt[v];
            -- cnt[lca];
            if (upper(curLCA, lca))
            {
                ++ cnt[curLCA];
                -- cnt[lca];
                curLCA = lca;
            }
        }

        a.clear();
    }

    DFS_calc(1, 1);
    if (res.size() > 0) sort(res.begin(), res.end());
    cout << res.size() << "\n";
    for (int id : res) cout << id << " ";

    return 0;
}

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