Submission #1160698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160698		AlgorithmWarrior	Railway (BOI17_railway)	C++20	100 / 100	151 ms	34760 KiB

railway

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
int const LOG=20;
int n,m,k;
vector<int>tree[MAX];
int euler[MAX];
int pos[MAX];
int h[MAX];
int rmq[MAX][LOG];
int logar[MAX];
int used[MAX];
int query[MAX];
struct edge{
    int u,v;
}edg[MAX];

void read(){
    cin>>n>>m>>k;
    int i;
    for(i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
        edg[i]={u,v};
    }
}

void dfs(int nod,int tata){
    static int time=0;
    euler[++time]=nod;
    pos[nod]=time;
    for(auto fiu : tree[nod])
        if(fiu!=tata){
            h[fiu]=h[nod]+1;
            dfs(fiu,nod);
            euler[++time]=nod;
        }
}

void get_rmq(){
    int i,j;
    for(i=1;i<2*n;++i)
        rmq[i][0]=euler[i];
    for(j=1;j<LOG;++j)
        for(i=1;i<2*n;++i){
            rmq[i][j]=rmq[i][j-1];
            int urm=i+(1<<(j-1));
            if(urm<2*n){
                int rmq1=rmq[i][j];
                int rmq2=rmq[urm][j-1];
                if(h[rmq1]>h[rmq2])
                    rmq[i][j]=rmq2;
            }
        }
    for(i=2;i<MAX;++i)
        logar[i]=logar[i/2]+1;
}

int get_lca(int nod1,int nod2){
    int pos1=pos[nod1];
    int pos2=pos[nod2];
    if(pos1>pos2)
        swap(pos1,pos2);
    int len=pos2-pos1+1;
    int loga=logar[len];
    int rmq1=rmq[pos1][loga];
    int rmq2=rmq[pos2-(1<<loga)+1][loga];
    if(h[rmq1]<h[rmq2])
        return rmq1;
    else
        return rmq2;
}

void add_path(int nod,int anc){
    ++used[nod];
    --used[anc];
}

bool cmp(int nod1,int nod2){
    return pos[nod1]<pos[nod2];
}

void process_queries(){
    int i;
    for(i=1;i<=m;++i){
        int sz;
        cin>>sz;
        int j;
        for(j=1;j<=sz;++j)
            cin>>query[j];
        sort(query+1,query+sz+1,cmp);
        for(j=2;j<=sz;++j)
            add_path(query[j],get_lca(query[j],query[j-1]));
        add_path(query[1],get_lca(query[1],query[sz]));
    }
}

int dfs_path(int nod,int tata){
    for(auto fiu : tree[nod])
        if(fiu!=tata)
            used[nod]+=dfs_path(fiu,nod);
    return used[nod];
}

void get_answer(){
    vector<int>ans;
    int i;
    for(i=1;i<n;++i){
        auto [nod,par]=edg[i];
        if(h[nod]<h[par])
            swap(nod,par);
        if(used[nod]>=k)
            ans.push_back(i);
    }
    cout<<ans.size()<<'\n';
    for(auto elem : ans)
        cout<<elem<<' ';
}

int main()
{
    read();
    dfs(1,0);
    get_rmq();
    process_queries();
    dfs_path(1,0);
    get_answer();
    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