제출 #1268848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268848		Davdav1232	Railway (BOI17_railway)	C++20	0 / 100	1096 ms	20928 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;
vi euler;
vector<vector<vii>> G;
vi path_to_par;

void dfs(int u, int p){
    euler.push_back(u);
    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 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 c, b;
        cin>>c>>b;
        G[c-1].push_back({b-1, i+1});
        G[b-1].push_back({c-1, i+1});
    }
    
    //root from 0.
    dfs(0, 0);
    //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