Submission #1273460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273460		DeathIsAwe	Railway (BOI17_railway)	C++20	100 / 100	134 ms	25172 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
vector<vector<pair<int,int>>> graph(100001);
int parent[100001][20], depth[100001], weight[100001], order[100001];
int c = 0;


int tpow(int a) {
    int val = 1;
    for (int i=0;i<a;i++) {
        val *= 2;
    } return val;
}


void dfs(int a, int b) {
    depth[a] = b;
    order[a] = c;
    for (pair<int,int> i: graph[a]) {
        if (i.ff != parent[a][0]) {
            parent[i.ff][0] = a;
            c += 1;
            dfs(i.ff, b + 1);
        }
    }
}


bool comp(int a, int b) {
    return order[a] < order[b];
}


bool compdepth(int a, int b) {
    return depth[a] > depth[b];
}


int lca(int a, int b) {
    if (depth[a] < depth[b]) {
        swap(a, b);
    }
    
    int diff = depth[a] - depth[b];
    for (int i=19;i>-1;i--) {
        if ((diff & tpow(i))) a = parent[a][i];
    }
    if (a == b) return a;

    for (int i=19;i>-1;i--) {
        if (parent[a][i] != parent[b][i]) {
            a = parent[a][i];
            b = parent[b][i];
        }
    }
    return parent[a][0];
}


int main() {
    //cin.tie(0)->sync_with_stdio(false);
    for (int i=0;i<100001;i++) {
        weight[i] = 0;
    }


    int n, m, k, d1, d2; cin >> n >> m >> k;
    for (int i=0;i<n-1;i++) {
        cin >> d1 >> d2; d1--; d2--;
        graph[d1].push_back(mp(d2, i));
        graph[d2].push_back(mp(d1, i));
    }
    vector<vector<int>> ministers(m);


    for (int i=0;i<m;i++) {
        cin >> d1;
        for (int j=0;j<d1;j++) {
            cin >> d2; d2--;
            ministers[i].push_back(d2);
        }
    }


    parent[0][0] = 0;
    dfs(0, 0);
    for (int i=1;i<20;i++) {
        for (int j=0;j<n;j++) {
            parent[j][i] = parent[parent[j][i - 1]][i - 1];
        }
    }


    //for (int i=0;i<n;i++) {
    //    cout << i << ' ' << depth[i] << '\n';
    //} cout << '\n';
    //for (int i=0;i<n;i++) {
    //    cout << i << ' ' << order[i] << '\n';
    //} cout << '\n';
    

    for (int i=0;i<m;i++) {
        sort(ministers[i].begin(), ministers[i].end(), comp);
        int top = ministers[i][0];
        weight[ministers[i][0]] += 1;
        for (int j=1;j<(int)ministers[i].size();j++) {
            weight[ministers[i][j]] += 1;
            int sus = lca(ministers[i][j], ministers[i][j - 1]);
            weight[sus] -= 1;
            top = lca(top, ministers[i][j]);
        }
        weight[top] -= 1;
        //for (int i=0;i<n;i++) {
        //    cout << weight[i] << ' ';
        //} cout << '\n';
    }


    vector<int> botsort;
    for (int i=0;i<n;i++) botsort.pb(i);
    sort(botsort.begin(), botsort.end(), compdepth);
    vector<int> ansvec;
    for (int i: botsort) {
        for (pair<int,int> j: graph[i]) {
            if (j.ff != parent[i][0] && weight[j.ff] >= k) {
                ansvec.pb(j.ss);
            }
            if (j.ff != parent[i][0]) {
                weight[i] += weight[j.ff];
            }
        }
    }
    

    sort(ansvec.begin(), ansvec.end());
    cout << ansvec.size() << '\n';
    for (int i: ansvec) {
        cout << i + 1 << ' ';
    }
}

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