Submission #1277863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277863		ngocphu	Railway (BOI17_railway)	C++20	100 / 100	88 ms	24552 KiB

railway

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxN = 1e5 + 4;
const int LOG = 18;

int n, m, k, high[maxN], par[maxN][LOG + 1], pos[maxN], c[maxN], a[maxN], dp[maxN], cnt = 0;
vector<int> E[maxN];
pair<int,int> edge[maxN];

void dfs(int u)
{
    pos[u] = ++cnt;
    for (int id : E[u])
    {
        int v = edge[id].first + edge[id].second - u;
        if (v == par[u][0]) continue;

        c[v] = id;
        high[v] = high[u] + 1;
        par[v][0] = u;
        dfs(v);
    }
}

int lca(int u, int v)
{
    if (high[v] > high[u]) return lca(v, u);

    for (int i = LOG; i >= 0; --i)
    {
        if (high[par[u][i]] >= high[v])
        {
            u = par[u][i];
        }
    }

    if (u == v) return u;

    for (int i = LOG; i >= 0; --i)
    {
        if (par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];
        }
    }

    return par[u][0];
}

struct cmp
{
    bool operator() (int a, int b)
    {
        return pos[a] < pos[b];
    }
};

void dfs2(int u)
{
    for (int id : E[u])
    {
        int v = edge[id].first + edge[id].second - u;
        if (v == par[u][0]) continue;

        dfs2(v);
        dp[u] += dp[v];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    // freopen(".INP","r",stdin);
    // freopen(".OUT","w",stdout);

    cin >> n >> m >> k;

    for (int i = 1; i <= n - 1; ++i)
    {
        int u, v; cin >> u >> v;

        E[u].push_back(i);
        E[v].push_back(i);

        edge[i] = make_pair(u, v);
    }

    dfs(1);

    for (int j = 1; j <= LOG; ++j)
    {
        for (int i = 1; i <= n; ++i)
        {
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }

    high[0] = -1;

    for (int i = 1; i <= m; ++i)
    {
        int sz; cin >> sz;

        for (int j = 1; j <= sz; ++j) cin >> a[j];

        sort(a + 1, a + sz + 1, cmp());

        for (int j = 1; j < sz; ++j)
        {
            int u = a[j];
            int v = a[j + 1];
            int t = lca(u, v);

            dp[u]++;
            dp[v]++;
            dp[t] -= 2;
        }

        int u = a[1];
        int v = a[sz];
        int t = lca(u, v);

        dp[u]++;
        dp[v]++;
        dp[t] -= 2;
    }

    dfs2(1);

    vector<int> ans;

    for (int i = 1; i <= n; ++i)
    {
        int id = c[i];

        if (dp[i] >= k * 2)
        {
            ans.push_back(id);
        }
    }

    cout << ans.size() << "\n";

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

    for (int x : ans) cout << x << " ";

    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