Submission #1096459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096459		kingdragon	Railway (BOI17_railway)	C++14	23 / 100	1071 ms	524288 KiB

railway

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iil pair<ll,ll>
#define iiil pair<ll,pair<ll,ll>>
#define oo 1e18
#define check(n) (prime[n>>6]&(1<<((n&63)>>1)))
#define set(n) prime[n>>6]|=(1<<((n&63)>>1))
using namespace std;
const int N=2e5+5;
const ll Mod=1e9+7;
const ll MOD=13141702292180207;
const int dx[]={-1,0,0,1};
const int dy[]={0,-1,1,0};


int n,m,k,g[N],par[N][19],LOG=17, depth[N];
vector<ii> a[N];
set<int> d[N], dp[N];
vector<int> res;
void dfs(int u)
{
    for (ii i: a[u])
    {
        int v=i.F;
        if (v==par[u][0]) continue;
        par[v][0]=u;
        g[v]=i.S;
        depth[v]=depth[u]+1;
        dfs(v);
    }
}

int lca(int u,int v)
{
    if (depth[u]<depth[v]) swap(u,v);
    for (int i=LOG;i>=0;i--)
        if (depth[par[u][i]]>=depth[v]) u=par[u][i];
    
    if (u==v) return v;
    for (int i=LOG;i>=0;i--)
    {
        if (par[u][i]!=par[v][i]) 
        {
            u=par[u][i];
            v=par[v][i];
        }
    }
    return par[v][0];
}

void dfs2(int u)
{
    for (ii i: a[u])
    {
        if (i.F==par[u][0]) continue;
        dfs2(i.F);
        for (int j: d[i.F]) d[u].insert(j);
    }
    for (int i: dp[u]) d[u].erase(i);
    if (d[u].size()>=k) res.pb(g[u]);
    // if (u==3)
    // {
    //     cout << u << '\n';
    //     for (int i: d[u]) cout << i << ' ';
    // }
    // cout << '\n';
}
void slove()
{
    cin >> n >> m >> k;
    for (int i=1;i<n;i++)
    {
        int u,v;
        cin >> u >> v;
        a[u].pb(ii(v,i));
        a[v].pb(ii(u,i));
    }
    g[1]=0; depth[1]=1;
    par[1][0]=0;
    dfs(1);
    for (int j=1;j<=LOG;j++)
        for (int i=1;i<=n;i++) par[i][j]=par[par[i][j-1]][j-1];
    
    for (int j=1;j<=m;j++)
    {
        int x, u, v;
        cin >> x;
        for (int i=1;i<=x;i++)
        {
            cin >> u;
            d[u].insert(j);
            if (i==1) v=u;
            else v=lca(v,u);
        }
        dp[v].insert(j);
    }

    dfs2(1);
    cout << res.size() << '\n';
    sort(res.begin(),res.end());
    for (int i: res) cout << i << ' ';
}
int main()
{
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
    int T=1;
    //cin >> T;
    while(T--) slove();
}

Compilation message (stderr)

railway.cpp: In function 'void dfs2(int)':
railway.cpp:65:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |     if (d[u].size()>=k) res.pb(g[u]);
      |         ~~~~~~~~~~~^~~
railway.cpp: In function 'void slove()':
railway.cpp:91:19: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |         int x, u, v;
      |                   ^

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