Submission #395903

#	Time	Username	Problem	Language	Result	Execution time	Memory
395903		Peti	Railway (BOI17_railway)	C++14	100 / 100	137 ms	28056 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int logn = 20;

vector<vector<pair<int, int>>> g;
vector<vector<int>> lca;
vector<int> h1, h2, ert;
vector<bool> volt;

int hely = 0;
void bejar(int akt, int os){
    volt[akt] = true;
    h1[akt] = hely++;
    lca[akt][0] = os;
    for(pair<int, int> e : g[akt])
        if(!volt[e.first])
            bejar(e.first, akt);
    h2[akt] = hely++;
    return;
}

int get_lca(int a, int b){
    if(h1[a] > h1[b]) swap(a, b);
    if(h1[a] < h1[b] && h2[b] < h2[a])
        return a;
    for(int i = logn-1; i >= 0; i--)
        if(h2[lca[a][i]] < h2[b])
            a = lca[a][i];
    return lca[a][0];
}

vector<int> ki;
int bejar2(int akt, int k, int el){
    volt[akt] = true;
    int ret = ert[akt];
    for(pair<int, int> e : g[akt])
        if(!volt[e.first])
            ret += bejar2(e.first, k, e.second);
    if(ret >= k)
        ki.push_back(el);
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin>>n>>m>>k;

    g.resize(n);
    h1.resize(n);
    h2.resize(n);
    ert.resize(n, 0);
    volt.assign(n, false);
    lca.resize(n, vector<int>(logn));

    for(int i = 0; i < n-1; i++){
        int a, b;
        cin>>a>>b;
        g[a-1].emplace_back(b-1, i+1);
        g[b-1].emplace_back(a-1, i+1);
    }

    bejar(0, 0);
    for(int j = 1; j < logn; j++)
        for(int i = 0; i < n; i++)
            lca[i][j] = lca[lca[i][j-1]][j-1];

    for(int i = 0; i < m; i++){
        int a;
        cin>>a;
        vector<int> v(a);
        for(int &x : v){
            cin>>x;
            x--;
        }

        sort(v.begin(), v.end(), [](int a, int b){ return h1[a] < h1[b];});
        int ind = -1;
        if(v.size() > 1)
            ert[v[0]]++;
        for(int j = 1; j < (int)v.size(); j++){
            int x = get_lca(v[j-1], v[j]);
            if(ind == -1 || h1[x] < h1[ind])
                ind = x;
            ert[x]--;
            ert[v[j]]++;
        }
        if(ind != -1)
            ert[ind]--;
    }

    volt.assign(n, false);
    bejar2(0, k, -1);

    sort(ki.begin(), ki.end());
    cout<<ki.size()<<"\n";
    for(int x : ki)
        cout<<x<<" ";
    cout<<"\n";

    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