Submission #871935

#	Time	Username	Problem	Language	Result	Execution time	Memory
871935		12345678	Railway (BOI17_railway)	C++17	100 / 100	122 ms	38468 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=17;
int n, m, k, pa[nx][kx], lvl[nx], ed[nx], hv[nx], in[nx], out[nx], rv[nx], t, u, v, x, lc, sz[nx], cnt;
bool dp[nx];
vector<pair<int, int>> d[nx];
vector<int> add[nx], erase[nx];
queue<int> q;
set<int> ans;

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    in[u]=++t;
    rv[t]=u;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, id]:d[u]) 
    {
        if (v==p) continue;
        ed[v]=id; dfs(v, u); sz[u]+=sz[v];
        if (sz[v]>sz[hv[u]]) hv[u]=v;
    }
    sz[u]++;
    out[u]=t;
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return u;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

void insert(int u)
{
    for (auto tmp:add[u]) if (!dp[tmp]) dp[tmp]=1, cnt++;
}

void remove(int u)
{
    for (auto tmp:erase[u]) if (dp[tmp]) dp[tmp]=0, cnt--;
}

void dfs2(int u, int p, bool del)
{
    for (auto [v, id]:d[u]) if (v!=p&&v!=hv[u]) dfs2(v, u, 1);
    if (hv[u]) dfs2(hv[u], u, 0);
    for (auto [v, id]:d[u]) if (v!=p&&v!=hv[u]) for (int i=in[v]; i<=out[v]; i++) insert(rv[i]);
    for (auto [v, id]:d[u]) if (v!=p&&v!=hv[u]) for (int i=in[v]; i<=out[v]; i++) remove(rv[i]);
    insert(u);
    remove(u);
    if (u!=1&&cnt>=k) ans.insert(ed[u]);
    if (del)
    {
        cnt=0;
        for (int i=in[u]; i<=out[u]; i++) for (auto tmp:add[rv[i]]) dp[tmp]=0;
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>k;
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back({v, i}), d[v].push_back({u, i});
    dfs(1, 1);
    for (int i=1; i<=m; i++)
    {
        cin>>x>>u;
        lc=u;
        add[u].push_back(i);
        for (int j=0; j<x-1; j++) cin>>u, lc=lca(lc, u), add[u].push_back(i);
        erase[lc].push_back(i);
    }
    for (int i=1; i<=n; i++) sz[i]=add[i].size()+erase[i].size();
    dfs2(1, 1, 0);
    cout<<ans.size()<<'\n';
    for (auto tmp:ans) cout<<tmp<<' ';
}

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