Submission #751005

#	Time	Username	Problem	Language	Result	Execution time	Memory
751005		sofija6	Railway (BOI17_railway)	C++14	100 / 100	144 ms	39000 KiB

railway

#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
#define logn 18
using namespace std;
ll c[MAXN],t=2,up[MAXN][logn],in[MAXN],out[MAXN],k;
vector<pair<ll,ll> > G[MAXN];
vector<ll> ans;
void DFS(ll i,ll p)
{
    in[i]=t;
    t++;
    up[i][0]=p;
    for (ll j=1;j<logn;j++)
        up[i][j]=up[up[i][j-1]][j-1];
    for (auto next : G[i])
    {
        if (next.first!=p)
            DFS(next.first,i);
    }
    out[i]=t;
    t++;
}
bool Is_Ancestor(ll u,ll v)
{
    return in[u]<=in[v] && out[u]>=out[v];
}
ll LCA(ll u,ll v)
{
    if (Is_Ancestor(u,v))
        return u;
    if (Is_Ancestor(v,u))
        return v;
    for (ll i=logn-1;i>=0;i--)
    {
        if (!Is_Ancestor(up[u][i],v))
            u=up[u][i];
    }
    return up[u][0];
}
bool Cmp(ll x,ll y)
{
    return in[x]<in[y];
}
struct bit
{
    vector<ll> v;
    void Init()
    {
        v.resize(2*MAXN);
    }
    void Add(ll pos,ll val)
    {
        for (ll i=pos;i<2*MAXN;i+=i&(-i))
            v[i]+=val;
    }
    ll Calc(ll pos)
    {
        ll cur=0;
        for (ll i=pos;i>0;i-=i&(-i))
            cur+=v[i];
        return cur;
    }
    ll Query(ll l,ll r)
    {
        return Calc(r)-Calc(l-1);
    }
};
bit B;
void DFS_Solve(ll i,ll p)
{
    for (auto next : G[i])
    {
        if (next.first!=p)
        {
            if (B.Query(in[next.first],out[next.first])>=2*k)
                ans.push_back(next.second);
            DFS_Solve(next.first,i);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,a,b,s;
    cin >> n >> m >> k;
    for (ll i=1;i<n;i++)
    {
        cin >> a >> b;
        G[a].push_back({b,i});
        G[b].push_back({a,i});
    }
    DFS(1,1);
    B.Init();
    for (ll i=1;i<=m;i++)
    {
        cin >> s;
        for (ll j=1;j<=s;j++)
            cin >> c[j];
        sort(c+1,c+1+s,Cmp);
        c[s+1]=c[1];
        for (ll j=2;j<=s+1;j++)
        {
            ll l=LCA(c[j-1],c[j]);
            B.Add(in[l],-2);
            B.Add(in[c[j-1]],1);
            B.Add(in[c[j]],1);
        }
    }
    DFS_Solve(1,1);
    sort(ans.begin(),ans.end());
    cout << ans.size() << "\n";
    for (ll i : ans)
        cout << i << " ";
    return 0;
}

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