Submission #871782

#	Time	Username	Problem	Language	Result	Execution time	Memory
871782		12345678	Railway (BOI17_railway)	C++17	23 / 100	1071 ms	524288 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, f, lc;
vector<pair<int, int>> d[nx];
vector<int> add[nx], erase[nx], ans;
set<int> s[nx];

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);
}

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)
{
    for (auto [v, id]:d[u]) 
    {
        if (v!=p)
        {
            dfs2(v, u);
            if (s[v].size()>=k) ans.push_back(id);
            for (auto tmp:s[v]) s[u].insert(tmp);
        }
    }
    for (auto tmp:add[u]) s[u].insert(tmp);
    for (auto tmp:erase[u]) s[u].erase(tmp);
}

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);
    }
    dfs2(1, 1);
    sort(ans.begin(), ans.end());
    cout<<ans.size()<<'\n';
    for (auto tmp:ans) cout<<tmp<<' ';
}

Compilation message (stderr)

railway.cpp: In function 'void dfs2(int, int)':
railway.cpp:35:28: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |             if (s[v].size()>=k) ans.push_back(id);
      |                 ~~~~~~~~~~~^~~

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