Submission

PPPPPPPPPP

Score: 100

User: mydKN

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

Language: cpp

Time: 0.003 second

Submitted On: 2024-12-05 22:06:21

#include<bits/stdc++.h>

using namespace std;

const int maxn = 310;
const int LOG = 9;

int n, m;
int arr[maxn];
int parent[maxn];
int l[maxn], r[maxn];
vector<int> root;
vector<int> vec[maxn];
int height[maxn];
int dp[maxn][LOG];

void preprocessLCA(){
    for(int i=1;i<=n;++i){
        dp[i][0] = parent[i];
    }
    for(int j=1;(1<<j)<=n;++j){
        for(int i=1;i<=n;++i){
            dp[i][j] = dp[dp[i][j-1]][j-1];
        }
    }
}

int LCA(int u, int v){
    if(height[u] < height[v]) swap(u, v);
    int diff = height[u] - height[v];
    for(int i=LOG-1;i>=0;--i){
        if((1<<i) & diff){
            u = dp[u][i];
        }
    }
    if(u == v) return u;
    for(int i =LOG-1;i>=0;--i){
        if(dp[u][i] != dp[v][i]){
            u = dp[u][i];
            v = dp[v][i];
        }
    }
    return parent[u];
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	cin >> l[1] >> r[1];
	int cnt = 0;
	int nowparent = 1;
	parent[1] = 1;
	root.emplace_back(1);
	for(int i=2;i<=n;++i){
		cin >> l[i] >> r[i];
		if(l[i] > r[nowparent]){
			nowparent = i;
			root.emplace_back(i);
			cnt = -1;
		}
		else height[i] = height[nowparent] + 1;
		parent[i] = nowparent;
		int j = cnt;
		while(j > 0){
			if(l[i] > l[nowparent+j] && r[i] < r[nowparent+j]){
				parent[i] = nowparent + j;
				height[i] = height[nowparent + j] + 1;
				break;
			}
			--j;
		}
		++cnt;
	}
	preprocessLCA();
	int res = 0;
	for(int i=0;i<m;++i){
		int x;
		cin >> x;
		for(auto e : root){
			if(l[x] >= l[e] && r[x] <= r[e]){
				if(vec[e].empty()) res++;
				vec[e].emplace_back(x);
			}
		}
	}
	cout << res << "\n";
	int lca;
	for(int i=0;i<n;++i){
		if(!vec[i].empty()){
			lca = vec[i][0];
			for(int j=1;j<vec[i].size();++j){
				lca = LCA(lca, vec[i][j]);
			}
			cout << lca << " ";
		}
	}
	// for(int i=0;i<n;++i){
	// 	if(!vec[i].empty()){
	// 		cout << i << " : ";
	// 		for(auto e : vec[i]) cout << e << " ";
	// 		cout << "\n";
			
	// 	}
	// }
	// for(int i=1;i<=n;++i) cout << i << " ";
	// cout << "\n";
	// for(int i=1;i<=n;++i) cout << parent[i] << " ";
	// cout << "\n";
	// for(int i=1;i<=n;++i) cout << height[i] << " ";
	// cout << "\n";
	// for(auto e : root) cout << e << " ";
}