Submission #1263473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263473		_HDH	Railway (BOI17_railway)	C++20	36 / 100	60 ms	26556 KiB

railway

#include <bits/stdc++.h>

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 1606
#endif

using namespace std;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define pc __builtin_popcount
#define bit(i) 1LL << i

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef string str;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef array<int, 3> iii;
typedef array<ll, 3> lll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
typedef vector<db> vd;

template<typename T> T gcd(T a, T b){return (b == 0? a : gcd(b, a % b));}
template<typename T> T lcm(T a, T b){return a / gcd(a, b) * b;}
template<typename T> T mod(T a, T m){if (a < 0) return a + m; if (a >= m) a -= m; if (a < m) return a; return a % m;}
template<typename T> T minimize(T &x, T const &v){if (x == -1 || x > v){x = v; return true;} return false;}
template<typename T> T maximize(T &x, T const &v){if (x == -1 || x < v){x = v; return true;} return false;}

#define file "fiel"
bool const SINGLE_TEST = true;

int const N = 1e5 + 1;
int const L = 19;
int const M = 5e4 + 1;

int n, m, k;
vector<ii> g[N];
vector<int> s[M];

int trv_id = 0;
int h[N], trv[N], d[N], p[N][L], sz[N], id[N];

void upd(int x, int v){
    for (;x < N; x += x & -x)
        d[x] += v;
}

int get(int x){
    int ans = 0;
    for (;x > 0; x -= x & -x)
        ans += d[x];
    return ans;
}

void DFS(int v){
    trv[v] = ++trv_id;
    for (auto u: g[v]) if (u.st != p[v][0]){
        h[u.st] = h[v] + 1;
        p[u.st][0] = v;
        for (int i = 1; i < L; i++){
            p[u.st][i] = p[p[u.st][i - 1]][i - 1];
        }
        id[u.st] = u.nd; 
        // cerr << v << " to " << u.st << "\n";
        DFS(u.st);
        sz[v] += sz[u.st];
    }
    sz[v]++;
}

int LCA(int a, int b){
    if (h[a] < h[b])
        swap(a, b);
    int k = h[a] - h[b];

    for (int i = 0; i < L; i++)
        if (k & (1 << i))
            a = p[a][i];

    if (a == b)
        return a;

    for (int i = L - 1; i >= 0; i--)
        if (p[a][i] != p[b][i])
            a = p[a][i], b = p[b][i];

    return p[a][0];
}

void solve(){
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        g[a].pb({b, i});
        g[b].pb({a, i});
    }

    for (int i = 0; i < m; i++){
        int si; cin >> si;
        for (int j = 0; j < si; j++){
            int x; cin >> x;
            s[i].pb(x);
        }
    }

    DFS(1);

    for (int i = 0; i < m; i++){
        sort(s[i].begin(), s[i].end(), [](int a, int b){return trv[a] < trv[b];});
        s[i].pb(s[i][0]);

        for (int j = 0; j < s[i].size() - 1; j++){
            int lca = LCA(s[i][j], s[i][j + 1]);
            upd(trv[s[i][j]], 1);
            upd(trv[s[i][j + 1]], 1);
            upd(trv[lca], -2);
        }
        
    }

    vector<int> ans;
    for (int i = 1; i <= n; i++){
        // cerr << get(trv[i] + sz[i] - 1) << " - " << get(trv[i] - 1) << " = " << get(trv[i] + sz[i] - 1) - get(trv[i] - 1) << "\n";
        if (get(trv[i] + sz[i] - 1) - get(trv[i] - 1) >= 2 * k){
            ans.push_back(id[i]);
        }
        
    }

    cout << ans.size() << "\n";
    for (auto x: ans)
        cout << x << " ";
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);//      the
    cin.tie(0);cout.tie(0);// 	    magical lines
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    int t;
    if (SINGLE_TEST) t = 1;
    else cin >> t;
    while (t--) solve();
    return 0;
}
/*
khong phai _HDH, _HDH ko xai template!!!
> [00:01] (-07:00) 24.August.2025
*/

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