Submission #1312779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312779		Born_To_Laugh	Railway (BOI17_railway)	C++17	0 / 100	49 ms	23040 KiB

railway

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;

const int maxn = 1e5 + 10;
int n, m, k;
vector<pair<int,int>> adj[maxn];
vector<int> ans;
int eid[maxn], tin[maxn], val[maxn];
int dep[maxn];
int binlift[maxn][20];
int id = 0;

void dfs(int a, int par){
    tin[a] = ++id;
    for(auto &edge: adj[a]){
        int elm = edge.fi;
        if(elm == par)continue;
        
        binlift[elm][0] = a;
        for(int i=1; i<20; ++i){
            binlift[elm][i] = binlift[binlift[elm][i - 1]][i - 1];
        }

        eid[elm] = edge.se;
        dep[elm] = dep[a] + 1;

        dfs(elm, a);
    }
}
void dfscal(int a, int par){
    for(auto &edge: adj[a]){
        int elm = edge.fi;
        if(elm == par)continue;
        val[a] += val[elm];
        dfscal(elm, a);
    }
    if(val[a] >= 2 * k && a != 1)ans.push_back(eid[a]);
}
int lca(int a, int b){
    if(dep[a] < dep[b])swap(a, b);
    int k = dep[a] - dep[b];
    for(int i=0; i<20; ++i){
        if(k & (1 << i))a = binlift[a][i];
    }
    if(a == b)return a;
    for(int i=19; i>=0; --i){
        if(binlift[a][i] != binlift[b][i]){
            a = binlift[a][i];
            b = binlift[b][i];
        }
    }
    return binlift[a][0];
}
void solve(){
    cin >> n >> m >> k;
    for(int i=1; i<n; ++i){
        int a, b;cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    dfs(1, -1);
    for(int i=1; i<=m; ++i){
        int x;cin >> x;
        vector<int> sth(x + 1, 0);
        for(int j=1; j<=x; ++j)cin >> sth[j];

        sort(sth.begin() + 1, sth.end(), [&](int a, int b){
            return tin[a] < tin[b];
        });

        for(int j=1; j<=x; ++j){
            int b, a = sth[j];
            if(j == x)b = sth[1];
            else b = sth[j + 1];

            int c = lca(a, b);
            val[a]++;
            val[b]++;
            val[c] -= 2;
        }
    }
    dfscal(1, -1);
    sort(alle(ans));
    cout << ans.size() << '\n';
    for(auto &elm: ans)cout << elm << ' ';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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