Submission #871786

#	Time	Username	Problem	Language	Result	Execution time	Memory
871786		12345678	Railway (BOI17_railway)	C++17	7 / 100	97 ms	41808 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], u, v, x, lc, sz[nx], cnt;
bool vs[nx], 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;
    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) ed[v]=id, dfs(v, u), sz[u]+=sz[v];
    sz[u]++;
}

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 dfs2(int u, int p, int idx, bool del)
{
    pair<int, pair<int, int>> hv={0, {0, 0}};
    for (auto [v, id]:d[u]) if (v!=p) hv=max(hv, {sz[v], {v, id}});
    for (auto [v, id]:d[u]) if (v!=p&&v!=hv.second.first) dfs2(v, u, id, 1);
    if (hv.second.first!=0) dfs2(hv.second.first, u, hv.second.second, 0);
    for (auto [v, id]:d[u]) if (v!=p&&v!=hv.second.first) dfs2(v, u, id, 0);
    for (auto tmp:add[u]) if (dp[tmp]==0) cnt++, dp[tmp]=1, q.push(tmp);
    for (auto tmp:erase[u]) dp[tmp]=0, cnt--;
    if (!vs[idx]) 
    {
        vs[idx]=1;
        if (cnt>=k&&idx!=-1) ans.insert(idx);
    }
    //cout<<u<<' '<<p<<' '<<idx<<' '<<del<<' '<<cnt<<'\n';
    if (del) while (!q.empty()) dp[q.front()]=0, q.pop(), cnt=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, -1, 0);
    cout<<ans.size()<<'\n';
    for (auto tmp:ans) cout<<tmp<<' ';
}

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