Submission #1005231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005231		HasanV11010238	Railway (BOI17_railway)	C++17	100 / 100	166 ms	64304 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000000
int n, m, k, a, b, si, timer = 0;
vector<vector<int>> v, up, edg;
vector<int> p, val, de, tin;
map<vector<int>, int> ma; 
void getpar(int x, int pa, int depth){
    timer++;
    tin[x] = timer;
    p[x] = pa;
    de[x] = depth;
    if (x == 1){
        pa++;
    }
    up[x][0] = pa;
    for (int i = 1; i < 20; i++){
        up[x][i] = up[up[x][i - 1]][i - 1];
    }
    for (auto el : v[x]){
        if (el != pa){
            getpar(el, x, depth + 1);
        }
    }
}
int dist(int x, int k){
    for (int i = 19; i >= 0; i--){
        int v = k & (1<<i);
        if (v != 0){
            x = up[x][i];
        }
    }
    return x;
}
int lca(int a, int b){
    if (de[a] > de[b]){
        swap(a, b);
    }
    b = dist(b, de[b] - de[a]);
    if (a == b){
        return a;
    }
    for (int i = 19; i >= 0; i--){
        int jmpa = up[a][i];
        int jmpb = up[b][i];
        if (jmpa != jmpb){
            a = jmpa;
            b = jmpb;
        }
    }
    return up[a][0];
}
ll dfs(int x, int pa){
    int sch = 0;
    for (auto el : v[x]){
        if (el != pa){
            int res = dfs(el, x);
            if (res >= 2 * k){
                ma[{x, el}] = 1;
                ma[{el, x}] = 1;
            }
            sch += res;
        }
    }
    return sch + val[x];
}
int main(){
    cin>>n>>m>>k;
    v.resize(n + 1), p.resize(n + 1), up.assign(n + 1, vector<int>(20, 1)), de.assign(n + 1, 0), val.assign(n + 1, 0), tin.resize(n + 1);
    for (int i = 0; i < n  - 1; i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        edg.push_back({a, b});
    }
    getpar(1, 0, 0);
    for (int i = 0; i < m; i++){
        cin>>si;
        vector<vector<int>> so;
        for (int i = 0; i < si; i++){
            cin>>a;
            so.push_back({tin[a], a});
        }
        sort(so.begin(), so.end());
        for (int i = 0; i < si - 1; i++){
            a = so[i][1], b = so[i + 1][1];
            int lc = lca(a, b);
            val[lc] -= 2, val[a]++, val[b]++;
        }
        a = so[0][1], b = so[si - 1][1];
        int lc = lca(a, b);
        val[lc] -= 2, val[a]++, val[b]++;
    }
    dfs(1, 0);
    vector<int> ans;
    for (int i = 0; i < n - 1; i++){
        if (ma[edg[i]] == 1){
            ans.push_back(i + 1);
        }
    }
    cout<<ans.size()<<"\n";
    for (auto el : ans){
        cout<<el<<" ";
    }
}

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