Submission #606698

#	Time	Username	Problem	Language	Result	Execution time	Memory
606698		Hanksburger	Railway (BOI17_railway)	C++17	36 / 100	124 ms	28684 KiB

railway

#include <bits/stdc++.h>
using namespace std;
int par[100005][17], t[100005], d[100005], x[100005], r[100005], cnt[100005], tt;
vector<pair<int, int> > adj[100005];
vector<int> adj2[100005], vec, tor;
bool cmp(int u, int v)
{
    return (t[u]<t[v]);
}
int lca(int u, int v)
{
    if (d[u]<d[v])
        swap(u, v);
    int dif=d[u]-d[v];
    for (int i=16; i>=0; i--)
        if (dif&(1<<i))
            u=par[u][i];
    if (u==v)
        return u;
    for (int i=16; i>=0; i--)
    {
        if (par[u][i]!=par[v][i])
        {
            u=par[u][i];
            v=par[v][i];
        }
    }
    return par[u][0];
}
void dfs(int u, int p)
{
    t[u]=(++tt);
    par[u][0]=p;
    for (int i=1; i<=16; i++)
        par[u][i]=par[par[u][i-1]][i-1];
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first, w=adj[u][i].second;
        if (v!=p)
        {
            d[v]=d[u]+1;
            x[v]=w;
            dfs(v, u);
        }
    }
}
void dfs2(int u, int p)
{
    int sz=adj2[u].size();
    r[u]+=1-sz;
    for (int v:adj2[u])
        dfs2(v, u);
}
void dfs3(int u, int p)
{
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first;
        if (v!=p)
        {
            dfs3(v, u);
            r[u]+=r[v];
        }
    }
    cnt[x[u]]=r[u];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, k, ans=0;
    cin >> n >> m >> k;
    for (int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    dfs(1, 1);
    for (int i=1; i<=m; i++)
    {
        int s;
        cin >> s;
        vec.clear();
        tor.clear();
        for (int j=0; j<s; j++)
        {
            int u;
            cin >> u;
            vec.push_back(u);
        }
        sort(vec.begin(), vec.end(), cmp);
        int LCA=vec[0];
        for (int j=1; j<s; j++)
        {
            int u=vec[j-1], v=vec[j];
            int w=lca(u, v);
            if (w!=u)
                adj2[w].push_back(u);
            if (w!=v)
                adj2[w].push_back(v);
            tor.push_back(u);
            tor.push_back(v);
            tor.push_back(w);
            LCA=lca(LCA, vec[j]);
        }
        sort(tor.begin(), tor.end(), cmp);
        tor.resize(unique(tor.begin(), tor.end())-tor.begin());
        for (int u:tor)
        {
            sort(adj2[u].begin(), adj2[u].end(), cmp);
            adj2[u].resize(unique(adj2[u].begin(), adj2[u].end())-adj2[u].begin());
        }
        dfs2(tor[0], tor[0]);
        r[tor[0]]--;
        for (int u:tor)
            adj2[u].clear();
    }
    dfs3(1, 1);
    for (int i=1; i<n; i++)
        ans+=(cnt[i]>=k);
    cout << ans << '\n';
    for (int i=1; i<n; i++)
        if (cnt[i]>=k)
        cout << i << ' ';
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i=0; i<adj[u].size(); i++)
      |                   ~^~~~~~~~~~~~~~
railway.cpp: In function 'void dfs3(int, int)':
railway.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i=0; i<adj[u].size(); i++)
      |                   ~^~~~~~~~~~~~~~

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