Submission #734909

#	Time	Username	Problem	Language	Result	Execution time	Memory
734909		bgnbvnbv	Railway (BOI17_railway)	C++14	100 / 100	163 ms	38276 KiB

railway

#include<bits/stdc++.h>
#define TASKNAME "lcm"
#define pb push_back
#define pli pair<int,int>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);

using namespace std;
using ll=long long;
const ll maxN=2e5+1;
const ll INF=-1e10;
const ll mod=1e9+7;
ll h[maxN],p[maxN],par[maxN][20];
ll LCA(ll u, ll v)
{
    if(h[u]<h[v]) swap(u,v);
    ll log=log2(h[u])+1;
    for(int i=log;i>=0;i--)
    {
        if(h[par[u][i]]>=h[v]) u=par[u][i];
    }
    //cout << h[u]<<' '<< h[v]<<'\n';
    if(u==v) return u;
    for(int i=log;i>=0;i--)
    {
        if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
    }
    return p[u];
}
vector<pli>g[maxN];
ll in[maxN],tg=0;
#define fi first
#define se second
ll id[maxN],idx[maxN];
void dfs(ll u=1,ll pp=0)
{
    in[u]=++tg;
    for(auto v1:g[u])
    {
        ll v=v1.fi;
        ll i=v1.se;
        if(v!=pp)
        {
            id[i]=v;
            idx[v]=i;
            p[v]=par[v][0]=u;
            h[v]=h[u]+1;
            for(int j=1;j<=18;j++) par[v][j]=par[par[v][j-1]][j-1];
            dfs(v,u);
        }
    }
}
ll ans[maxN];
void dfs_lai(ll u=1,ll pp=0)
{
    for(auto v1:g[u])
    {
        ll v=v1.fi;
        ll i=v1.se;
        if(v!=pp)
        {
            dfs_lai(v,u);
            ans[u]+=ans[v];
        }
    }
}
bool cmp(ll x, ll y)
{
    return in[x]<in[y];
}
void tang(ll u,ll pp)
{
    ans[u]+=1;
    ans[pp]-=1;
}
ll n,m,k;
ll tmp[maxN];
void solve()
{
    cin >> n >> m >> k;
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb({v,i});
        g[v].pb({u,i});
    }
    p[1]=1;
    for(int i=0;i<=18;i++) par[1][i]=1;
    dfs();
    vector<ll> v;
    for(int i=1;i<=m;i++)
    {
        ll sz;
        v.clear();
        cin>> sz;
        for(int j=1;j<=sz;j++)
        {
            ll kk;
            cin >>kk;
            v.pb(kk);
        }
        stack<int> s;
        sort(v.begin(),v.end(),cmp);
        for(int j=0;j<v.size()-1;j++)
        {
            if(j==0)
            {
                ll x=LCA(v[0],v[1]);
                tmp[1]=x;
                tang(v[0],x);
                tang(v[1],x);
            }
            else
            {
                ll x=LCA(v[j],v[j+1]);
                ll u=v[j];
                ll vv=v[j+1];
                if(h[tmp[j]]>=h[x])
                {
                    tang(tmp[j],x);
                }
                tang(vv,x);
                if(h[tmp[j]]<h[x])
                {
                    x=tmp[j];
                }
                tmp[j+1]=x;
            }
        }
    }
    dfs_lai();
    vector<ll> ass;
    for(int i=1;i<n;i++)
    {
        ll u=id[i];
        if(ans[u]>=k)
        {
            ass.pb(i);
           // cout << ans[u]<<'\n';
        }
    }
    cout << ass.size()<<'\n';
    for(auto z:ass) cout << z<< ' ';
    //cout <<LCA(1,2) ;
}
int main()
{
    fastio
    //freopen(TASKNAME".IN","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    ll t=1;
    //cin >> t;
    while(t--)solve();
}

Compilation message (stderr)

railway.cpp: In function 'void dfs_lai(ll, ll)':
railway.cpp:58:12: warning: unused variable 'i' [-Wunused-variable]
   58 |         ll i=v1.se;
      |            ^
railway.cpp: In function 'void solve()':
railway.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int j=0;j<v.size()-1;j++)
      |                     ~^~~~~~~~~~~
railway.cpp:116:20: warning: unused variable 'u' [-Wunused-variable]
  116 |                 ll u=v[j];
      |                    ^

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