Submission #762844

#	Time	Username	Problem	Language	Result	Execution time	Memory
762844		ThegeekKnight16	Railway (BOI17_railway)	C++17	100 / 100	86 ms	26428 KiB

railway

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXK = 21;
array<int, MAXN> prof, paiEdge, tin, Marc;
array<array<int, MAXK>, MAXN> dp;
array<vector<pair<int, int>>, MAXN> grafo;
vector<int> resp;
int N, M, K;
int temp = 0;

void dfs(int v, int p, int edge)
{
    tin[v] = ++temp;
    prof[v] = prof[p]+1; paiEdge[v] = edge;
    dp[v][0] = p;
    for (int k = 1; k < MAXK; k++) dp[v][k] = dp[dp[v][k-1]][k-1];

    for (auto [viz, e] : grafo[v])
    {
        if (viz == p) continue;
        dfs(viz, v, e);
    }
}

int lca(int a, int b)
{
    if (prof[a] < prof[b]) swap(a, b);
    int jump = prof[a] - prof[b];
    for (int k = 0; k < MAXK; k++) if (jump & (1 << k)) a = dp[a][k];
    if (a == b) return a;
    for (int k = MAXK-1; k >= 0; k--)
        if (dp[a][k] != dp[b][k]) a = dp[a][k], b = dp[b][k];

    return dp[a][0];
}

void calcResp(int v, int p)
{
    // cerr << v << " " << Marc[v] << " " << paiEdge[v] << '\n';
    for (auto [viz, e] : grafo[v])
    {
        if (viz == p) continue;
        calcResp(viz, v);
        Marc[v] += Marc[viz];
    }
    // cerr << v << " " << Marc[v] << " " << paiEdge[v] << '\n';

    if (Marc[v] >= 2*K && paiEdge[v] > 0) resp.push_back(paiEdge[v]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> K;
    for (int i = 1; i < N; i++)
    {
        int X, Y;
        cin >> X >> Y;
        grafo[X].emplace_back(Y, i);
        grafo[Y].emplace_back(X, i);
    }
    dfs(1, 1, 0);

    for (int i = 1; i <= M; i++)
    {
        int S;
        cin >> S;
        vector<int> verts(S);
        for (auto &x : verts) cin >> x;
        sort(verts.begin(), verts.end(), [&](const int &a, const int &b) {return tin[a] < tin[b];});
        verts.push_back(verts[0]);
        for (int i = 0; i < S; i++)
        {
            // cerr << verts[i] << " " << verts[i+1] << " " << lca(verts[i], verts[i+1]) << '\n';
            Marc[verts[i]]++; Marc[verts[i+1]]++;
            Marc[lca(verts[i], verts[i+1])] -= 2;
        }
    }

    calcResp(1, 1);

    sort(resp.begin(), resp.end());
    cout << resp.size() << '\n';
    for (auto x : resp) cout << x << " ";
    cout << '\n';
}

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