제출 #1259210

#제출 시각아이디문제언어결과실행 시간메모리
1259210a5a7Railway (BOI17_railway)C++20
36 / 100
62 ms26048 KiB
#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];
    int time[n];
    int timer = 0;
    fill(depth, depth+n, 0);
    fill(edge, edge+n, -1);
    function<void(int,int)> dfs = [&](int x, int prev){
        up[x][0] = prev;
        time[x] = timer++;
        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]--;
        sort(r, r+s, [&](int x, int y){ return time[x] < time[y]; });
        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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...