Submission #1268841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268841		Davdav1232	Railway (BOI17_railway)	C++20	0 / 100	1097 ms	37828 KiB

railway

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> vii;
typedef long long ll;

int a=1;
int k=1;
vvi par;
vi dep;
vi euler;
vector<vector<vii>> G;
vi path_to_par;

void dfs(int u, int p){
    euler.push_back(u);
    par[u].push_back(p);
    dep[u]=dep[p]+1;
    for(int i=0; i<G[u].size(); i++){
        if(G[u][i].first==p){
            path_to_par[u]=G[u][i].second;
            continue;
        }
        dfs(G[u][i].first, u);
    }
    euler.push_back(p);
}

int lca(int u, int v){
    if(dep[u]<dep[v]) swap(u, v);
    int t=k-1;
    while(t>=0){
        if(dep[par[u][t]]>=dep[v]) u=par[u][t];
        t--;
    }
    if(u==v) return u;
    t=0;
    while(par[u][t]!=par[v][t]) t++;
    while(t>=0){
        if(par[u][t]!=par[v][t]){
            u=par[u][t];
            v=par[v][t];
        }
        t--;
    }
    return par[u][0];
}



int main() {
    int n, m, K;
    cin>>n>>m>>K;
    G.resize(n);
    path_to_par.resize(n);
    for(int i=0; i<n-1; i++){
        int a, b;
        cin>>a>>b;
        G[a-1].push_back({b-1, i+1});
        G[b-1].push_back({a-1, i+1});
    }
    
    //root from 0.
    while(a<=n-1){
        a*=2;
        k++;
    }
    dep.resize(n);
    par.resize(n);
    dep[0]=-1;
    dfs(0, 0);
    for(int i=1; i<k; i++){
        for(int j=0; j<n; j++){
            par[j].push_back(par[par[j][i-1]][i-1]);
        }
    }
    //find first and last time everything appears
    vi f(n, -1);
    vi l(n);
    for(int i=0; i<euler.size(); i++){
        if(f[euler[i]]==-1) f[euler[i]]=i;
        l[euler[i]]=i;
    }

    vvi S(m);
    for(int i=0; i<m; i++){
        int s;
        cin>>s;
        for(int j=0; j<s; j++){
            int a;
            cin>>a;
            S[i].push_back(a-1);
        }
    }
    vvi SS(m);
    for(int i=0; i<m; i++){
        for(int j=0; j<S[i].size(); j++){
            SS[i].push_back(f[S[i][j]]);
        }
        sort(SS[i].begin(), SS[i].end());
    }
    vi nodes;
    for(int i=1; i<n; i++){
        int count=0;
        for(int j=0; j<m; j++){
            if(SS[j][0]>=f[i] && SS[j][SS[j].size()-1]<=l[i]) continue;
            if(SS[j][0]>l[i] || SS[j][SS[j].size()-1]<f[i]) continue;
            int b=0, c=SS[j].size()-1;
            while(b+1<c){
                int d=(b+c)/2;
                if(SS[j][d]>=f[i]) c=d;
                else b=d;
            }
            if(SS[j][c]<=l[i]) count++;
            //find the first index with SS[j][t]>=f[i]
        }
        if(count>=K) nodes.push_back(i);
    }
    
    cout<<nodes.size()<<"\n";
    vi y;
    for(int i=0; i<nodes.size(); i++){
        y.push_back(path_to_par[nodes[i]]);
    }
    sort(y.begin(), y.end());
    for(int i=0; i<y.size(); i++) cout<<y[i]<<" ";
    return 0;
}

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