Submission #654891

#	Time	Username	Problem	Language	Result	Execution time	Memory
654891		rafatoa	Railway (BOI17_railway)	C++17	100 / 100	199 ms	44992 KiB

railway

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#pragma GCC optimize ("Ofast")

#define double ld

#define F first
#define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define rs resize
#define as assign
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define MP make_pair

#define int long long
const int INF = 4e18;
const int inf = 2e9;

struct segTree{
    int N;
    vi tree;
    segTree(int n){
        N = (1LL<<(int)ceil(log2(n)));
        tree = vi(2*N, 0);
    }
    void update(int k, int val){
        k += N;
        tree[k] += val;
        for(k /= 2; k >= 1; k /= 2)
            tree[k] = tree[2*k]+tree[2*k+1];
    }
    int query(int a, int b){
        a += N, b += N;
        int ans = 0;
        while(a <= b){
            if(a%2 == 1) ans += tree[a++];
            if(b%2 == 0) ans += tree[b--];
            a /= 2, b /= 2;
        }
        return ans;
    }
};

void solve(){
    int n, m, k; cin >> n >> m >> k;
    vector<vpi> adj(n+1);
    vvi up(n+1, vi(21));
    for(int i=0; i<n-1; i++){
        int u, v; cin >> u >> v;
        adj[u].pb({v, i+1}); adj[v].pb({u, i+1});
    }

    vi in(n+1), out(n+1), d(n+1), edpar(n+1);
    int time = 0;

    function<void(int)> dfs = [&](int s){
        in[s] = time++;
        for(auto [u, ed]:adj[s])
            if(u != up[s][0]){
                up[u][0] = s;
                d[u] = d[s]+1;
                edpar[u] = ed;
                dfs(u);
            }
        out[s] = time++;
    };
    dfs(1);

    for(int j=1; j<=20; j++)
    for(int i=1; i<=n; i++)
        up[i][j] = up[up[i][j-1]][j-1];

    function<int(int, int)> lca = [&](int a, int b){
        if(d[a] > d[b]) swap(a, b);
        
        for(int j=20; j>=0; j--)
            if((d[b]-d[a])&(1LL<<j))
                b = up[b][j];
        
        for(int j=20; j>=0; j--)
            if(up[a][j] != up[b][j])
                a = up[a][j], b = up[b][j];
        
        if(a == b) return a;
        return up[a][0];
    };

    segTree st(2*n);

    while(m--){
        int sz; cin >> sz;
        vi nod(sz); read(nod);
        sort(all(nod), [&](int a, int b){
            return (in[a] < in[b]);
        });
        nod.pb(nod[0]);

        for(int i=0; i<sz; i++){
            int p = lca(nod[i], nod[i+1]);
            st.update(in[p], -2);
            st.update(in[nod[i]], 1);
            st.update(in[nod[i+1]], 1);
        }
    }

    vi ans;
    for(int i=2; i<=n; i++)
        if(st.query(in[i], out[i]) >= 2*k)
            ans.pb(edpar[i]);
    
    cout << ans.size() << "\n";
    sort(all(ans));
    print(ans);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif

    solve();
    return 0;
}

/*stolen stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * READ CONSTRAINTS
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

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