제출 #1190689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190689		jahongir	Railway (BOI17_railway)	C++20	36 / 100	83 ms	21448 KiB

railway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,
					 tree_order_statistics_node_update>;
 
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()

const int mxn = 1e5+10, lg2 = 17;
vector<pi> g[mxn]; int qu[mxn];

int suc[mxn][lg2], val[mxn];
int tin[mxn], tout[mxn], tim;


struct BIT{
    int st[mxn],sz;
    void init(int n){
        sz = n;
    }
    void add(int i, int val){
        for(; i <= sz; i+=i&-i) st[i] += val;
    }
    int query(int l, int r){
        int res = 0;
        for(; r > 0; r -= r&-r) res += st[r];
        for(l--; l > 0; l -= l&-l) res -= st[l];
        return res;
    }
}bit;

void dfs(int u, int p){
    tin[u] = ++tim;
    suc[u][0] = p;
    for(int i = 1; i < lg2; i++) suc[u][i] = suc[suc[u][i-1]][i-1];

    for(auto [v,i] : g[u]) if(v!=p){
        val[v] = i;
        dfs(v,u);
    }

    tout[u] = tim;
}

bool isanc(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int getlca(int u, int v){
    if(isanc(u,v)) return u;
    if(isanc(v,u)) return v;
    for(int i = lg2-1; i >= 0; i--)
        if(!isanc(suc[u][i],v)) u = suc[u][i];
    return suc[u][0];
}


void solve(){
    int n,q,k; cin >> n >> q >> k;
    for(int i = 1; i < n; i++){
        int u,v; cin >> u >> v;
        g[u].pb({v,i}); g[v].pb({u,i});
    }
    dfs(1,1);
    bit.init(n);
    while(q--){
        int m; cin >> m;
        for(int i = 0; i < m; i++) cin >> qu[i];
        sort(qu,qu+m,[&](const int a, const int b) -> bool{
            return tin[a] < tin[b];
        });
        qu[m] = qu[0];

        for(int i = 0; i < m; i++){
            bit.add(tin[qu[i]],1);
            bit.add(tin[qu[i+1]],1);
            bit.add(tin[getlca(qu[i],qu[i+1])],-2);
        }
    }
    vector<int> ans;
    for(int i = 2; i <= n; i++)  if(bit.query(tin[i],tout[i]) >= 2*k) ans.pb(val[i]);

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


int main(){
    int t = 1;
    while(t--) solve();
}

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