Submission #1095809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095809		windowwife	Railway (BOI17_railway)	C++14	100 / 100	72 ms	49384 KiB

railway

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 2, LG = 21, blocksize = 450, mod = 1e9 + 7;
int n, q, k, u, v, s, a, d[maxn], t = 0, tin[maxn], tout[maxn], st[LG][maxn], ps[maxn], res = 0;
vector<int> ok, L;
vector<pair<int, int>> adj[maxn];
void dfs (int u, int p)
{
    tin[u] = ++t;
    st[0][u] = p;
    for (auto pp : adj[u])
    {
        int v = pp.first;
        if (v == p) continue;
        d[v] = d[u] + 1;
        dfs(v, u);
    }
    tout[u] = t;
}
bool cmp (int x, int y)
{
    return tin[x] < tin[y];
}
int lca (int u, int v)
{
    if (d[u] < d[v]) swap(u, v);
    int diff = d[u] - d[v];
    for (int j = LG - 1; j >= 0; j--)
        if (diff >= (1 << j))
        {
            diff -= (1 << j);
            u = st[j][u];
        }
    if (u == v) return u;
    for (int j = LG - 1; j >= 0; j--)
        if (st[j][u] != st[j][v])
        {
            u = st[j][u];
            v = st[j][v];
        }
    return st[0][u];
}
void dfs2 (int u, int p)
{
    for (auto pp : adj[u])
    {
        int v = pp.first, i = pp.second;
        if (v == p) continue;
        dfs2(v, u);
        if (ps[v] >= 2*k)
        {
            res++;
            L.push_back(i);
        }
        ps[u] += ps[v];
    }
}
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q >> k;
    for (int i = 1; i < n; i++)
    {
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    dfs(1, 0);
    for (int j = 1; j < LG; j++)
        for (int i = 1; i <= n; i++)
            st[j][i] = st[j - 1][st[j - 1][i]];
    while (q--)
    {
        ok.clear();
        cin >> s;
        while (s--)
        {
            cin >> a;
            ok.push_back(a);
        }
        sort(ok.begin(), ok.end(), cmp);
        ok.resize(unique(ok.begin(), ok.end()) - ok.begin());
        for (int i = 0; i < (int)ok.size(); i++)
        {
            int l = lca(ok[i], ok[(i + 1)%ok.size()]);
            ps[ok[i]]++;
            ps[l]--;
            ps[ok[(i + 1)%ok.size()]]++;
            ps[l]--;
        }
    }
    dfs2(1, 0);
    cout << res << '\n';
    sort(L.begin(), L.end());
    for (int i : L) cout << i << " ";
}

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