Submission #1135173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135173		a5a7	Railway (BOI17_railway)	C++20	36 / 100	73 ms	25536 KiB

railway

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
    vector<vector<pair<int,int>>> adj(n);
    for (int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        a--, b--;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    int depth[n];
    int up[n][20];
    int edge[n];
    fill(depth, depth+n, 0);
    fill(edge, edge+n, -1);
    function<void(int,int)> dfs = [&](int x, int prev){
        up[x][0] = prev;
        for (auto nxt : adj[x]){
            if (nxt.first == prev) continue;
            edge[nxt.first] = nxt.second;
            depth[nxt.first] = depth[x]+1;
            dfs(nxt.first, x);
        }
    };
    dfs(0, -1);
    for (int j = 1; j < 20; j++){
        for (int i = 0; i < n; i++){
            up[i][j] = up[i][j-1] == -1 ? -1 : up[up[i][j-1]][j-1];
        }
    }
    function<int(int,int)> lca = [&](int a, int b){
        if (depth[a]<depth[b]) swap(a,b);
        for (int i = 0; i < 20; i++){
            if ((1<<i)&(depth[a]-depth[b])) a = up[a][i];
        }
        if (a == b) return a;
        for (int i = 19; i > -1; i--){
            if (up[a][i] != up[b][i]){
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    };
    int add[n];
    int val[n];
    for (int i = 0; i < n; i++) add[i] = val[i] = 0;
    for (int i = 0; i < m; i++){
        int s; cin >> s;
        int r[s];
        for (int i = 0; i < s; i++) cin >> r[i], r[i]--;
        for (int i = 0; i < s; i++){
            int a = r[i], b = r[(i+1)%s];
            int c = lca(a, b);
            add[c] -= 2;
            val[a]++;
            val[b]++;
        }
    }
    int current = 0;
    function<void(int,int)> dfs2 = [&](int x, int prev){
        for (auto nxt : adj[x]){
            if (nxt.first == prev) continue;
            dfs2(nxt.first, x);
            val[x] += val[nxt.first];
        }
        val[x] += add[x];
    };
    dfs2(0, -1);
    vector<int> v;
    for (int i = 0; i < n; i++){
        if (val[i] >= 2*k){
            v.push_back(edge[i]);
        }
    }
    cout << v.size() << endl;
    for (int x : v) cout << x << " ";
    cout << endl;
}

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