제출 #893978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
893978		azosi	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	275 ms	33984 KiB

minmaxtree

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef pair<int, int> p;
const int inf = 1e9+7;

struct Query{
	int s, e, x, mx;
};

//Input / HLD - var
int in[70707], dep[70707], par[70707], top[70707], sz[70707];
vector<int> g[70707], inp[70707];
int chk[70707], pv, n, q;
vector<Query> qry;

//Get Answer - var
map<int, int> mp;
int cnt[70707], ans[70707];
int vis[70707];
vector<int> track[70707];

//Segment Tree - var
int treemin[1 << 18], treemax[1 << 18];
int tmpmin[1 << 18], tmpmax[1 << 18];
int mn[70707], mx[70707];

//Segment Tree - function
void pushmin(int node, int s, int e){
	if(tmpmin[node] == inf) return;
	treemin[node] = min(treemin[node], tmpmin[node]);
	if(s ^ e){
		tmpmin[node*2] = min(tmpmin[node], tmpmin[node*2]);
		tmpmin[node*2+1] = min(tmpmin[node], tmpmin[node*2+1]);
	}
	tmpmin[node] = inf;
}

void pushmax(int node, int s, int e){
	if(tmpmax[node] == -inf) return;
	treemax[node] = max(treemax[node], tmpmax[node]);
	if(s ^ e){
		tmpmax[node*2] = max(tmpmax[node], tmpmax[node*2]);
		tmpmax[node*2+1] = max(tmpmax[node], tmpmax[node*2+1]);
	}
	tmpmax[node] = -inf;
}

void updatemin(int node, int s, int e, int l, int r, int v){
	pushmin(node, s, e);
	if(r < s || e < l) return;
	if(l <= s && e <= r){
		treemin[node] = min(treemin[node], v);
		if(s ^ e){
			tmpmin[node*2] = min(tmpmin[node*2], v);
			tmpmin[node*2+1] = min(tmpmin[node*2+1], v);
		}
		return;
	}
	int m = s + e >> 1;
	updatemin(node*2, s, m, l, r, v);
	updatemin(node*2+1, m+1, e, l, r, v);
	treemin[node] = min(treemin[node*2], treemin[node*2+1]);
}

void updatemax(int node, int s, int e, int l, int r, int v){
	pushmax(node, s, e);
	if(r < s || e < l) return;
	if(l <= s && e <= r){
		treemax[node] = max(treemax[node], v);
		if(s ^ e){
			tmpmax[node*2] = max(tmpmax[node*2], v);
			tmpmax[node*2+1] = max(tmpmax[node*2+1], v);
		}
		return;
	}
	int m = s + e >> 1;
	updatemax(node*2, s, m, l, r, v);
	updatemax(node*2+1, m+1, e, l, r, v);
	treemax[node] = max(treemax[node*2], treemax[node*2+1]);
}

int querymin(int node, int s, int e, int l, int r){
	pushmin(node, s, e);
	if(r < s || e < l) return inf;
	if(l <= s && e <= r) return treemin[node];
	int m = s + e >> 1;
	int t1 = querymin(node*2, s, m, l, r);
	int t2 = querymin(node*2+1, m+1, e, l, r);
	return min(t1, t2);
}

int querymax(int node, int s, int e, int l, int r){
	pushmax(node, s, e);
	if(r < s || e < l) return -inf;
	if(l <= s && e <= r) return treemax[node];
	int m = s + e >> 1;
	int t1 = querymax(node*2, s, m, l, r);
	int t2 = querymax(node*2+1, m+1, e, l, r);
	return max(t1, t2);
}

//HLD - function
void dfs(int v = 1){
	chk[v] = 1;
	for(auto i : inp[v]){
		if(chk[i]) continue;
		chk[i] = 1;
		g[v].push_back(i);
		dfs(i);
	}
}

void dfs1(int v = 1){
	sz[v] = 1;
	for(auto &i : g[v]){
		dep[i] = dep[v] + 1; par[i] = v;
		dfs1(i); sz[v] += sz[i];
		if(sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
	}
}

void dfs2(int v = 1){
	in[v] = ++pv;
	for(auto i : g[v]){
		top[i] = i == g[v][0] ? top[v] : i;
		dfs2(i);
	}
}

void update(int a, int b, int op, int k){
	while(top[a] != top[b]){
		if(dep[top[a]] < dep[top[b]]) swap(a, b);
		int st = top[a];
		if(op == 1) updatemin(1, 1, n, in[st], in[a], k);
		else updatemax(1, 1, n, in[st], in[a], k);
		a = par[st];
	}
	if(dep[a] > dep[b]) swap(a, b);
	if(op == 1) updatemin(1, 1, n, in[a]+1, in[b], k);
	else updatemax(1, 1, n, in[a]+1, in[b], k);
}

//main
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; top[1] = 1;
	for(int i=2; i<=n; i++){
		int s, e; cin >> s >> e;
		inp[s].push_back(e);
		inp[e].push_back(s);
	}
	dfs(); dfs1(); dfs2();

	cin >> q;
	for(int i=1; i<(1 << 18); i++){
		tmpmin[i] = inf;
		tmpmax[i] = -inf;
		treemin[i] = inf;
		treemax[i] = -inf;
	}
	for(int i=0; i<q; i++){
		char op; int a, b, c;
		cin >> op >> a >> b >> c;
		if(op == 'm') update(a, b, 2, c);
		else update(a, b, 1, c);
		qry.push_back({a, b, c, op == 'M'});
	}

	for(int i=0; i<q; i++) mp[qry[i].x] = i;
	for(int i=2; i<=n; i++){
		mn[i] = querymax(1, 1, n, in[i], in[i]);
		mx[i] = querymin(1, 1, n, in[i], in[i]);
		if(mn[i] != -inf){
			cnt[mp[mn[i]]]++;
			track[mp[mn[i]]].push_back(i);
		}
		if(mx[i] != inf){
			cnt[mp[mx[i]]]++;
			track[mp[mx[i]]].push_back(i);
		}
	}

	memset(chk, 0, sizeof chk);
	priority_queue< p, vector<p>, greater<p> > pq;
	for(int i=0; i<q; i++) pq.push({cnt[mp[qry[i].x]], i});
	while(!pq.empty()){
		pair<int, int> now = pq.top();
		pq.pop();
		if (now.x != cnt[now.y]) continue;
		vis[now.y] = true;
		for(int i : track[now.y]){
			if(chk[i]) continue;
			ans[i] = qry[now.y].x;
			chk[i] = true;
			if(qry[now.y].mx){
				if (mn[i] != -inf) {
					cnt[mp[mn[i]]]--;
					if (!vis[mp[mn[i]]]) pq.push({cnt[mp[mn[i]]], mp[mn[i]]});
				}
			}else{
				if(mx[i] != inf){
					cnt[mp[mx[i]]]--;
					if (!vis[mp[mx[i]]]) pq.push({cnt[mp[mx[i]]], mp[mx[i]]});
				}
			}
			break;
		}
	}
	for(int i=2; i<=n; i++) if(!chk[i]) ans[i] = mn[i];
	for(int i=2; i<=n; i++){
		cout << par[i] << " " << i << " " << ans[i] << "\n";
	}
}

컴파일 시 표준 에러 (stderr) 메시지

minmaxtree.cpp: In function 'void updatemin(int, int, int, int, int, int)':
minmaxtree.cpp:63:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |  int m = s + e >> 1;
      |          ~~^~~
minmaxtree.cpp: In function 'void updatemax(int, int, int, int, int, int)':
minmaxtree.cpp:80:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |  int m = s + e >> 1;
      |          ~~^~~
minmaxtree.cpp: In function 'int querymin(int, int, int, int, int)':
minmaxtree.cpp:90:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |  int m = s + e >> 1;
      |          ~~^~~
minmaxtree.cpp: In function 'int querymax(int, int, int, int, int)':
minmaxtree.cpp:100:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |  int m = s + e >> 1;
      |          ~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42