Submission #1282886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282886		dhuyyyy	Railway (BOI17_railway)	C++20	0 / 100	66 ms	49232 KiB

railway

 #include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 1e5+5;
const ll INF = 1e18;
const int MOD = 1e9+7;

int n, q, k, u, v, timer = 0;

// RMQ
int st[18][2 * N];

// euler tour
int tin[N], tout[N], b[2 * N], id[2 * N];

// tree
vector<ii> adj[N];

// queries
int a[N], pre[N];
vector <int> res;

bool inside(int u,int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
bool cmp(int a,int b){
    return tin[a] < tin[b];
}
void dfs(int u,int p){
    tin[u] = ++timer;
    b[timer] = tin[u];
    id[timer] = u;
    for (ii it : adj[u]){
        if (it.fi == p) continue;
        dfs(it.fi,u);
        b[++timer] = tin[u];
    }
    tout[u] = timer;
}
void precompute_RMQ(){
    for (int i = 1; i <= timer; i++) st[0][i] = b[i];
    for (int j = 1; j <= 17; j++){
        for (int i = 1; i + (1 << j) - 1 <= timer; i++){
            st[j][i] = min(st[j - 1][i],st[j - 1][i + (1 << (j - 1))]);
        }
    }
}
int LCA(int u,int v){
    int l = tin[u];
    int r = tin[v];
    if (l > r) swap(l,r);
    int k = __lg(r - l + 1);
    return id[min(st[k][l],st[k][r - (1 << k) + 1])];
}
void solve(){
    cin >> k;
    for (int i = 1; i <= k; i++) cin >> a[i];
    sort(a+1,a+1+k,cmp);
    for (int i = 1; i < k; i++){
        a[i + k] = LCA(a[i],a[i + 1]);
    }
    k = 2 * k - 1;
    sort(a+1,a+1+k,cmp);
    k = unique(a+1,a+1+k) - a - 1;
    stack<int> st;
    st.push(a[1]);
    for (int i = 1; i <= k; i++){
        while (!inside(st.top(),a[i])){
            st.pop();
        }
        pre[a[i]]++;
        pre[st.top()]--;
        st.push(a[i]);
    }
}
void dp(int u,int p){
    for (ii it : adj[u]){
        if (it.fi == p) continue;
        dp(it.fi,u);
        if (pre[it.fi] >= k) res.push_back(it.se);
        pre[u] += pre[it.fi];
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> q >> k;
    for (int i = 1; i < n; i++){
        cin >> u >> v;
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
    }
    dfs(1,0);
    precompute_RMQ();
    while (q--){
        solve();
    }
    dp(1,0);
    sort(res.begin(),res.end());
    res.erase(unique(res.begin(),res.end()),res.end());
    cout << (int)res.size() << '\n';
    for (int it : res) cout << it << ' ';
    return 0;
}

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