Submission #445966

#	Time	Username	Problem	Language	Result	Execution time	Memory
445966		prvocislo	Railway (BOI17_railway)	C++17	100 / 100	199 ms	23356 KiB

railway

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 5, logn = 17;
int n, m, k, l[logn][maxn], tin[maxn], d[maxn], sum[maxn], id[maxn], timer = 0;
vector<pair<int, int> > g[maxn];
void dfs1(int u)
{
    tin[u] = timer++;
    for (int i = 1; i < logn; i++) l[i][u] = l[i-1][l[i-1][u]];
    for (pair<int, int> v : g[u])
    {
        if (v.first == l[0][u]) continue;
        l[0][v.first] = u, d[v.first] = d[u] + 1;
        id[v.first] = v.second;
        dfs1(v.first);
    }
}
int lca(int a, int b)
{
    if (d[a] < d[b]) swap(a, b);
    for (int i = logn-1; i >= 0; i--) if (d[l[i][a]] >= d[b]) a = l[i][a];
    if (a==b) return a;
    for (int i = logn-1; i >= 0; i--) if (l[i][a] ^ l[i][b]) a = l[i][a], b = l[i][b];
    return l[0][a];
}
vector<int> ans;
void dfs2(int u)
{
    for (pair<int, int> v : g[u]) if (v.first ^ l[0][u]) 
    {
        dfs2(v.first);
        sum[u] += sum[v.first];
    }
    if (sum[u] >= k) ans.push_back(id[u]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0, a, b; i < n-1; i++)
    {
        cin >> a >> b, a--, b--;
        g[a].push_back({b, i+1}), g[b].push_back({a, i+1});
    }
    dfs1(0);
    for (int i = 0; i < m; i++)
    {
        int s; cin >> s;
        vector<pair<int, int> > v(s);
        for (int j = 0; j < s; j++) cin >> v[j].second, sum[--v[j].second]++, v[j].first = tin[v[j].second];
        sort(v.begin(), v.end());
        int root = v[0].second;
        for (int j = 1; j < s; j++)
        {
            int l = lca(v[j-1].second, v[j].second);
            root = lca(root, v[j].second);
            sum[l]--;
        }
        sum[root]--;
    }
    dfs2(0);
    cout << ans.size() << "\n";
    sort(ans.begin(), ans.end());
    for (int i : ans) cout << i << " ";
    cout << "\n";
    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