Submission

Score: 100

User: exoworldgd

Problemset: ถังดักนิวทริโน

Language: cpp

Time: 0.002 second

Submitted On: 2025-05-23 22:10:13

#include <bits/stdc++.h>
#define pii pair<int,int>
#define exoworldgd cin.tie(nullptr)->sync_with_stdio(false),cout.tie(0)
using namespace std;
vector<vector<int>> tree(301);
vector<int> depth(301),tin(301),tout(301);
int up[301][10], t = 0; // up[301][10] because 2^(10-1) = 512
// binary lifting
void dfs(int u, int p) {
    tin[u] = t++;
    up[u][0] = p;
    for (int i = 1; i < 10; i++) up[u][i] = up[up[u][i-1]][i-1];
    for (int v : tree[u]) {
        depth[v] = depth[u] + 1;
        dfs(v,u);
    }
    tout[u] = t++;
}
// check if ancestor
bool yes(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }
// lowest common ancestor
int lca(int u, int v) {
	// bruh its like dsu "if (sz[x] < sz[y]) swap(x,y)"
    if (depth[u] < depth[v]) swap(u,v);
    int diff = depth[u]-depth[v];
    // using bitwise cause why not
    for (int i = 0; i < 10; i++) if (diff & (1 << i)) u = up[u][i];
    // bruh cycle detection type sht "if (x == y) return false;"
    if (u == v) return u;
    // binary lifting
    for (int i = 9; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}
int main(void) {
    exoworldgd;
    int n,m;
    cin >> n >> m;
    stack<pii> s;
    vector<vector<int>> path(301);
	vector<int> parent(301),height(301),ans;
    s.push({INT_MAX,0}); // dummy var
    // creating tree from bucket
    for (int i = 1; i<= n; i++) {
    	int l,r;
    	cin >> l >> r;
    	// if bucket outside interval create new component
    	while (l >= s.top().first) s.pop();
    	path[s.top().second].push_back(i);
    	s.push({r,i});
	}
	// adj list
	for (int u = 1; u <= n; u++) for (int v : path[u]) tree[u].push_back(v);
	for (int i = 1; i <= n; i++){
        if(up[i][0] == 0){
            depth[i] = 0;
            dfs(i,0);
        }
    }
    vector<int> a(m);
    for (int i  =0 ; i <m ;i++) cin >> a[i];
    // sort in dfs traversal order
    sort(a.begin(),a.end(),[&](int x, int y){return tin[x] < tin[y];});
    int curr = a[0];
    // lca sweep
    for (int i = 1; i <m ; i++) {
    	int w1 = a[i], w2= lca(curr,w1);
    	if (w2 == 0) {
    		ans.push_back(curr);
    		curr = w1;
		}
		else curr = w2;
	}
	ans.push_back(curr);
	sort(ans.begin(),ans.end());
	cout << ans.size() << '\n';
	for (int i : ans) cout << i << " ";
}