PS/BOJ
백준 2820번: 자동차 공장 (C++)
도비(Doby)
2022. 3. 19. 19:03
https://www.acmicpc.net/problem/2820
2820번: 자동차 공장
상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다.
www.acmicpc.net
Solved By: Euler Tour Technique, Segment Tree, Lazy Propagation
상사와 부하의 관계는 트리 구조로 나타낼 수 있으며 업데이트마다 DFS를 사용하기엔 N, M의 범위가 커서 시간 초과가 걸릴 가능성이 큽니다. Euler Tour Technique을 사용하여 트리를 Segment Tree처럼 만들어서 구간별로 업데이트한다면 시간을 확실하게 줄일 수 있습니다.
또한, 이때의 update는 구간을 update 해야 하는데 보통의 세그먼트 트리에서 구간을 업데이트하면 O(nlogn)이 걸리므로 시간 초과가 납니다. 이를 위해 Lazy Propagation까지 사용합니다.
>> 구간 업데이트 O(logn)
#include <iostream>
#include <vector>
#include <utility>
#define MAX (500000 + 1)
#define pii pair<int, int>
#define ll long long
using namespace std;
int n, m;
vector<int> adj[MAX];
pii ett[MAX];
ll money[MAX];
ll sgTree[MAX * 4];
ll lazy[MAX * 4];
vector<ll> result;
int dfsN = 0;
void dfs(int now, int par){
ett[now].first = ++dfsN;
for(int i = 0; i < adj[now].size(); i++){
int next = adj[now][i];
if(next == par) continue;
dfs(next, par);
}
ett[now].second = dfsN;
}
void lazyUpdate(int start, int end, int node){
if(!lazy[node]) return;
sgTree[node] += lazy[node];
if(start != end) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
void update(int start, int end, int node, int left, int right, ll val){
lazyUpdate(start, end, node);
if(end < left || start > right) return;
if(left <= start && end <= right){
if(start == end){
sgTree[node] += val;
}
else{
lazy[node * 2] += val;
lazy[node * 2 + 1] += val;
}
return;
}
int mid = (start + end) >> 1;
update(start, mid, node * 2, left, right, val);
update(mid + 1, end, node * 2 + 1, left, right, val);
}
ll query(int start, int end, int node, int idx){
lazyUpdate(start, end, node);
if(idx < start || end < idx) return 0;
if(start == end) return sgTree[node];
int mid = (start + end) >> 1;
return query(start, mid, node * 2, idx)
+ query(mid + 1, end, node * 2 + 1, idx);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> money[i];
if(i == 1) continue;
int v; cin >> v;
adj[v].push_back(i);
}
dfs(1, 0);
for(int i = 1; i <= n; i++){
update(1, n, 1, ett[i].first, ett[i].first, money[i]);
}
/*
// Euler Tour Technique Check
for(int i = 1; i <= n; i++){
cout << ett[i].first << ' ' << ett[i].second << '\n';
}
*/
for(int i = 0; i < m; i++){
char q;
cin >> q;
if(q == 'p'){
int a, w;
cin >> a >> w;
update(1, n, 1, ett[a].first + 1, ett[a].second, w);
// 자신을 제외한 부하들의 월급이기 때문에
// ett[a].first에다가 +1을 해준다.
}
else{
int a;
cin >> a;
result.push_back(query(1, n, 1, ett[a].first));
}
}
for(int i = 0; i < result.size(); i++){
cout << result[i] << '\n';
}
return 0;
}