KU01_Bucket Editorial
Monday, October 25, 2021, 03:44 PM
KU01_Bucket Editorial
จากโจทย์ จาก Input เราได้รับ จุดของถัง l ถึง r โดยไม่ได้รับประกันว่าในทุกๆ i จะเรียงกัน เราจึงจำเป็นต้องทำอัลกอริทึมเส้นกวาด (Sweepline Algorithm)
vector<pair<int, int>> line;
for(int i=1; i<=n; ++i){
cin >> l >> r;
line.emplace_back(l, i);
line.emplace_back(r, i);
}
sort(line.begin(), line.end());
line จะเก็บ event point ของอัลกอริทึมเส้นกวาดไว้
จากนั้นเราจะทำ LCA (Lowest Common Ancestor) เพื่อหาถังที่ต้องหยิบก่อนที่จำทำ LCA ได้นั้นเราต้องสร้างกราฟก่อนโดยสามารถ implement ได้จาก stack และเก็บ root ของแต่ละ component ไว้
vector<int> adj[333]; //Adjacency List
stack<int> st;
set<int> root;
for(auto x: line){
if(st.empty()){
st.push(x.second);
}
else if(st.top() != x.second){
adj[st.top()].push_back(x.second);
st.push(x.second)
}
else{
st.pop();
}
}
ส่วนตอนรับถังที่ต้องการเราสามารถ mark ไว้ได้
while(q--){
cin >> idx;
dp[idx] = 1;
}
เราจะทำ dynamic programmin on tree เพื่อหา LCA ได้อย่างง่ายดาย
void dfs(int u){
for(auto x: adj[u]){
dfs(x);
dp[u] += dp[x];
}
if(dp[u] > res){
res = dp[u];
pos = u;
}
}
set<int> ans;
for(auto x: root){
res = 0;
dfs(x);
if(res != 0){
ans.insert(pos);
}
}
Full Solution in C++
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[333];
int dp[333], res, pos;
void dfs(int u){
for(auto x: adj[u]){
dfs(x);
dp[u] += dp[x];
}
if(dp[u] > res){
res = dp[u];
pos = u;
}
}
int main(){
cin.tie(nullptr)->ios::sync_with_stdio(false);
int n, q, l, r, idx;
cin >> n >> q;
vector<pair<int, int>> line;
for(int i=1; i<=n; ++i){
cin >> l >> r;
line.emplace_back(l, i);
line.emplace_back(r, i);
}
sort(line.begin(), line.end());
stack<int> st;
set<int> root, ans;
for(auto x: line){
if(st.empty()){
st.push(x.second);
root.insert(x.second);
}
else if(st.top() != x.second){
adj[st.top()].push_back(idx);
st.push(x.second);
}
else{
st.pop();
}
}
while(q--){
cin >> idx;
dp[idx] = 1;
}
for(auto x: root){
res = 0;
dfs(x);
if(res != 0){
ans.insert(pos);
}
}
cout << ans.size() << "\n";
for(auto x: ans){
cout << x << " ";
}
return 0;
}
author