Submission #536694

#	Time	Username	Problem	Language	Result	Execution time	Memory
536694		__Variatto	Railway (BOI17_railway)	C++17	100 / 100	126 ms	25604 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10, L=18;
int n, m, k, jump[MAX][L+2], gle[MAX], pre[MAX];
vector<pair<int,int>>g[MAX], akt;
int czas=1;
void dfs(int v, int oj){
    jump[v][0]=oj;
    pre[v]=czas++;
    for(int i=1; i<=L; i++)
        jump[v][i]=jump[jump[v][i-1]][i-1];
    for(auto s:g[v]){
        if(s.fi!=oj){
            gle[s.fi]=gle[v]+1;
            dfs(s.fi, v);
        }
    }
}
int LCA(int a, int b){
    if(gle[b]>gle[a]) swap(a, b);
    for(int i=L; i>=0; i--)
        if(gle[jump[a][i]]>=gle[b])
            a=jump[a][i];
    if(a==b) return a;
    int wyn=a;
    for(int i=L; i>=0; i--){
        if(jump[a][i]==jump[b][i])
            wyn=jump[a][i];
        else
            a=jump[a][i], b=jump[b][i];
    }
    return wyn;
}
int dod[MAX], usu[MAX], suma[MAX];
vector<int>wynik;

void dfs2(int v, int oj, int ind){
    for(auto s:g[v]){
        if(s.fi!=oj){
            dfs2(s.fi, v, s.se);
            suma[v]+=suma[s.fi];
        }
    }
    suma[v]+=dod[v]-usu[v];
    if(suma[v]>=k*2) wynik.pb(ind);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1; i<=n-1; i++){
        int a, b;
        cin>>a>>b;
        g[a].pb({b, i}), g[b].pb({a, i});
    }
    dfs(1, 1);
    for(int i=1; i<=m; i++){
        int s, x;
        cin>>s;
        akt.clear();
        for(int j=1; j<=s; j++){
            cin>>x;
            akt.pb({pre[x], x});
        }
        sort(akt.begin(), akt.end());
        int last=0;
        for(auto a: akt){
            if(last){
                int lca=LCA(last, a.se);
                dod[last]++, dod[a.se]++, usu[lca]+=2;
            }
            last=a.se;
        }
        if(akt.size()>=2){
            int lca=LCA(akt[0].se, akt.back().se);
            dod[akt.back().se]++, dod[akt[0].se]++, usu[lca]+=2;
        }
    }
    dfs2(1, 1, 0);
    cout<<wynik.size()<<"\n";
    sort(wynik.begin(), wynik.end());
    for(auto a:wynik)
        cout<<a<<" ";
    cout<<"\n";
}

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