Submission #128855

#	Time	Username	Problem	Language	Result	Execution time	Memory
128855		Abelyan	Railway (BOI17_railway)	C++17	52 / 100	384 ms	30088 KiB

railway

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=1e5+10;
const ll MOD=1e9+7;

int n,m,k,lg,timer,tin[N],tout[N],anc[N][20],qan[N],subsz[N],tin2[N],timer2,ver[N],comp[N],deep[N],ttt,hakatin2[N];
bool all[4*N];
vector<pir> g[N];
vector<int> ans,poxel;

void dfs(int v,int par=0){
    tin[v]=timer++;
    anc[v][0]=par;
    FORT(i,1,lg) anc[v][i]=anc[anc[v][i-1]][i-1];
    deep[v]=deep[par]+1;
    trav(tv,g[v]){
        int to=tv.fr;
        if (to==par){
            continue;
        }
        dfs(to,v);
    }
    tout[v]=timer++;
}

bool upper(int a,int b){
    return tin[a]<=tin[b] && tout[b]<=tout[a];
}

int lca(int a,int b){
    if (upper(a,b))return a;
    if (upper(b,a))return b;
    FORD(i,lg+1){
        if (!upper(anc[a][i],b)){
            a=anc[a][i];
        }
    }
    return anc[a][0];
}

int dfs2(int v,int par=0){
    int tiv=qan[v];
    //cout<<v<<" "<<tiv<<endl;
    trav(tv,g[v]){
        int to=tv.fr;
        if (to==par)continue;
        int cur=dfs2(to,v);
        if (cur>=k){
            ans.ad(tv.sc);
        }
        tiv+=cur;
    }
    return tiv;
}

int dfssz(int v,int par=0){
    subsz[v]=1;
    trav(tv,g[v]){
        int to=tv.fr;
        if (to==par)continue;
        subsz[v]+=dfssz(to,v);
    }
    return subsz[v];
}

int cnt=1;
pir sg[4*N];

void update(int v,int tl,int tr,int ind,pir val){
    poxel.ad(v);
    if (tl==tr){
        sg[v]=val;
        return;
    }
    int tm=(tl+tr)/2;
    if (ind<=tm)update(v+v,tl,tm,ind,val);
    else update(v+v+1,tm+1,tr,ind,val);
    if (sg[v+v+1].fr==1)sg[v]=sg[v+v+1];
    else sg[v]=sg[v+v];
    //if (sg[v].sc==1){cout<<"stex el ka "<<tl<<" "<<tr<<" "<<ind<<endl;}
    //if (tl==0 && tr==2)cout<<"stex piti urish lini "<<sg[v].fr<<" "<<sg[v].sc<<endl;
}

pir query(int v,int tl,int tr,int l,int r){
    poxel.ad(v);
    if (l>r)return {0,0};
    //cout<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl;
    if (all[v]==ttt){
        //cout<<"heeey "<<hakatin2[r]<<endl;
        return {1,hakatin2[r]};
    }
    if (tl==l && tr==r){
        //if (sg[v].sc==1) cout<<"arraaaa stexa "<<v<<" "<<tl<<" "<<tr<<endl;
        all[v]=ttt;
        pir nax=sg[v];
        sg[v]={1,hakatin2[tr]};
        return nax;
    }
    int tm=(tl+tr)/2;
    pir q1=query(v+v+1,tm+1,tr,max(tm+1,l),r);
    if (sg[v+v+1].fr==1)sg[v]=sg[v+v+1];
    else sg[v]=sg[v+v];
    if (q1.fr==1){
        return q1;
    }
    q1 = query(v+v,tl,tm,l,min(r,tm));
    if (sg[v+v+1].fr==1)sg[v]=sg[v+v+1];
    else sg[v]=sg[v+v];
    return q1;
}

int get(int a){
    //cout<<"heeeeeeey  "<<a<<" "<<tin2[1]<<" "<<tin2[a]<<endl;
    while(true){
        int ca=comp[a];
        //cout<<ca<<endl;
        //cout<<ca<<" "<<ver[ca]<<" "<<tin2[ver[ca]]<<endl;;
        pir cur=query(1,0,n-1,tin2[ver[ca]],tin2[a]);
        if (cur.fr==1){
            return cur.sc;
        }
        a=anc[ver[ca]][0];
    }
    //cout<<"byeeeeee "<<endl;
    return 0;
}

void decomp(int v,int par,int ham){
    comp[v]=ham;
    tin2[v]=timer2++;
    //cout<<"haka "<<timer2-1<<" "<<v<<endl;
    hakatin2[timer2-1]=v;
    pir mx={INT_MIN,INT_MIN};
    FOR(i,g[v].size()){
        int to=g[v][i].fr;
        if (to==par)continue;
        mx=max(mx,{subsz[to],i});
    }
    if (mx.fr==INT_MIN)return;
    swap(g[v][0],g[v][mx.sc]);
    trav(tv,g[v]){
        int to=tv.fr;
        if (to==par)continue;
        if (to==g[v][0].fr){
            decomp(to,v,ham);
        }
        else{
            ver[cnt]=to;
            decomp(to,v,cnt++);
        }
    }
}


int main(){
    fastio;
    srng;
    cin>>n>>m>>k;
    FOR(i,n-1){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        g[a].ad({b,i+1});
        g[b].ad({a,i+1});
    }
    dfssz(0);
    ver[0]=0;
    deep[0]=-1;
    decomp(0,0,0);
    while((1<<lg)<=n)lg++;
    dfs(0);
    for(ttt=1;ttt<=m;ttt++){
        int s;
        cin>>s;
        vector<pir> vec;
        FOR(i,s){
            int a;
            cin>>a;
            a--;
            vec.ad({deep[a],a});
        }

        sort(all(vec));

        int lc=vec[0].sc;
        FORT(i,1,s-1){
            lc=lca(lc,vec[i].sc);
        }
        update(1,0,n-1,tin2[lc],{1,lc});
        FOR(i,s){
            qan[vec[i].sc]++;
            int verevin=get(vec[i].sc);
            qan[verevin]--;
            //cout<<vec[i].sc<<" "<<verevin<<endl;
            //update(1,0,n-1,tin2[vec[i].sc],{1,vec[i].sc});
        }
        trav(tv,poxel){
            sg[tv]={0,0};
        }
        poxel.clear();

    }
    assert(dfs2(0)==0);
    cout<<ans.size()<<endl;
    sort(all(ans));
    FOR(i,ans.size()){
        cout<<ans[i]<<" ";
    }
    return 0;
}
/*
10 3 2
1 2
1 5
1 8
2 3
2 4
5 6
5 7
8 9
8 10
6 2 4 8 1 10 9
3 2 4 3
3 9 5 10

9 4 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
3 4 2 6
4 1 5 2 3
3 5 7 9
2 6 8
*/

Compilation message (stderr)

railway.cpp: In function 'void decomp(int, int, int)':
railway.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
railway.cpp:156:5: note: in expansion of macro 'FOR'
     FOR(i,g[v].size()){
     ^~~
railway.cpp: In function 'int main()':
railway.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
railway.cpp:229:5: note: in expansion of macro 'FOR'
     FOR(i,ans.size()){
     ^~~

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