Submission #1199676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199676		huangallen	Railway (BOI17_railway)	C++20	100 / 100	121 ms	95152 KiB

railway

#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,sse4,bmi2,popcnt")
#define int long long
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define RREP1(i,n) for(int i=(n);i>=1;i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)((x).size()))
#define SQ(x) ((x)*(x))
#define pii pair<int,int>
#define pipii pair<int,pii>
#define ppi pair<pii,int>
#define Graph vector<vector<int>>
#define Graphw vector<vector<pii>>
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define md(x) (((x)%(mod)+(mod))%(mod))
#define MD(x,M) (((x)%(M)+(M))%(M))
#define ld long double
#define pdd pair<ld,ld>
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define addmod(x,y) x=((x+(y))%mod)
#define Vi vector<int>
#define Vpii vector<pii>
#ifdef LOCAL
#define op(x) cout<<(#x)<<"="<<(x)<<", ";
#define ope(x) cout<<(#x)<<"="<<(x)<<endl;
#define oparr(x) {cout<<(#x)<<":";for(auto allen:(x)) cout<<allen<<" ";cout<<" size="<<(x).size()<<endl;}
#define entr cout<<endl;
#else
#define op(x) ;
#define ope(x) ;
#define oparr(x) ;
#define entr ;
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& os,pair<T1,T2> p) { return os<<'{'<<p.f<<','<<p.s<<'}'; }
template<typename T1,typename T2>
istream& operator>>(istream& os,pair<T1,T2> &p) { return os>>p.f>>p.s; }
template<typename S>
ostream& operator<<(ostream& os,vector<S> p) { for(auto allen:p) os<<allen<<' ';return os<<'\n'; }
template<typename S>
istream& operator>>(istream& os,vector<S> &p) { for(auto &allen:p) os>>allen;return os; }
template<typename T1,typename T2>
pair<T1,T2> operator+(pair<T1,T2> p1,pair<T1,T2> p2) { return pair<T1,T2>(p1.f+p2.f,p1.s+p2.s); }
const int mod=998244353;
const int maxn=2e5+5;
const int maxb=20;
const int inf=1ll<<60;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rd(int l,int r) {
    return uniform_int_distribution<int>(l,r)(rng);
}
struct BIT {
    int n;
    Vi b;
    void init(int _n) {
        n=_n;
        b=Vi(n+1);
    }
    void _ud(int u,int v) {
        for(;u<=n;u+=u&-u) b[u]+=v;
    }
    void ud(int l,int r,int v)  {
        _ud(l,v);
        _ud(r+1,-v);
    }
    int qu(int u) {
        int r=0;
        for(;u>0;u-=u&-u) r+=b[u];
        return r;
    }
};
int n,m,k;
Graphw g;
Vi dfn,dfnp,dep;
Vpii dfn2;
Vi in,out,pe;
void dfs(int u,int fa) {
    dfnp[u]=SZ(dfn2);
    dfn2.pb({dep[u],u});
    for(auto [v,id]:g[u]) {
        if(v==fa) continue;
        pe[v]=id;
        in[id]=SZ(dfn);
        dfn.pb(id);
        dep[v]=dep[u]+1;
        dfs(v,u);
        out[id]=SZ(dfn);
        dfn.pb(id);
        dfn2.pb({dep[u],u});
    }
}
pii st[maxb][maxn];
void st_init() {
    int N=SZ(dfn2);
    REP(i,N) st[0][i]=dfn2[i];
    REP1(i,maxb-1) {
        REP(j,N) st[i][j]=min(st[i-1][j],st[i-1][min(N-1,j+(1<<i-1))]);
    }
}
int st_qu(int l,int r) {
    int lg=__lg(r-l+1);
    return min(st[lg][l],st[lg][r-(1<<lg)+1]).s;
}
int qu_lca(int a,int b) {
    if(dfnp[a]>dfnp[b]) swap(a,b);
    return st_qu(dfnp[a],dfnp[b]);
}
signed main() {
    IOS();
    cin>>n>>m>>k;
    g=Graphw(n);
    REP(i,n-1) {
        int u,v;
        cin>>u>>v,u--,v--;
        g[u].pb({v,i});
        g[v].pb({u,i});
    }
    dfn={-1};
    pe=in=out=dfnp=dep=Vi(n);
    dfs(0,-1);
    st_init();
    BIT bit;
    bit.init(n*2+10);
    auto upd_chain=[&](int a,int b,int v) {// a,b: node id
        // op(a)ope(b)
        bit.ud(a==0?1:in[pe[a]]+1,in[pe[b]],v);
    };
    auto qu_val=[&](int u) {// u:edge id
        return bit.qu(in[u])-bit.qu(out[u]);
    };
    // oparr(pe)
    // oparr(dfn)
    // oparr(dfnp)
    REP(i,m) {
        int s;
        cin>>s;
        Vi a(s);
        REP(j,s) cin>>a[j],a[j]--;
        sort(ALL(a),[&](int x,int y) {return dfnp[x]<dfnp[y]; });
        // oparr(a)
        Vi b;b.pb(a[0]);
        REP1(j,s-1) {
            // op(a[j-1])ope(a[j]);
            b.pb(qu_lca(a[j-1],a[j]));
            // op(i)ope(j)
            b.pb(a[j]);
        }
        // op(i)ope("ok")
        sort(ALL(b),[&](int x,int y) {return dfnp[x]<dfnp[y]; });
        b.erase(unique(ALL(b)),b.end());
        // oparr(b)
        REP1(j,SZ(b)-1) {
            upd_chain(qu_lca(b[j],b[j-1]),b[j],1);
        }
    }
    Vi an;
    // REP(i,n-1) cout<<qu_val(i)<<' ';entr
    REP(i,n-1) if(qu_val(i)>=k) an.pb(i);
    cout<<SZ(an)<<'\n';
    for(int x:an) cout<<x+1<<' ';
    cout<<'\n';
    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