oj.uz

Submission #893978

# Submission time Handle Problem Language Result Execution time Memory
893978 2023-12-27T18:10:51 Z azosi Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 275 ms 33984 KB 
#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";
	}
}

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11004 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 28984 KB Output is correct
2 Correct 198 ms 27108 KB Output is correct
3 Correct 203 ms 28324 KB Output is correct
4 Correct 179 ms 32708 KB Output is correct
5 Correct 187 ms 28088 KB Output is correct
6 Correct 208 ms 28612 KB Output is correct
7 Correct 161 ms 27892 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 19636 KB Output is correct
2 Correct 122 ms 19900 KB Output is correct
3 Correct 104 ms 23864 KB Output is correct
4 Correct 118 ms 25316 KB Output is correct
5 Correct 134 ms 21396 KB Output is correct
6 Correct 122 ms 21708 KB Output is correct
7 Correct 129 ms 20688 KB Output is correct
8 Correct 123 ms 20608 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11004 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 183 ms 28984 KB Output is correct
6 Correct 198 ms 27108 KB Output is correct
7 Correct 203 ms 28324 KB Output is correct
8 Correct 179 ms 32708 KB Output is correct
9 Correct 187 ms 28088 KB Output is correct
10 Correct 208 ms 28612 KB Output is correct
11 Correct 161 ms 27892 KB Output is correct
12 Correct 115 ms 19636 KB Output is correct
13 Correct 122 ms 19900 KB Output is correct
14 Correct 104 ms 23864 KB Output is correct
15 Correct 118 ms 25316 KB Output is correct
16 Correct 134 ms 21396 KB Output is correct
17 Correct 122 ms 21708 KB Output is correct
18 Correct 129 ms 20688 KB Output is correct
19 Correct 123 ms 20608 KB Output is correct
20 Correct 250 ms 27188 KB Output is correct
21 Correct 223 ms 25108 KB Output is correct
22 Correct 203 ms 25316 KB Output is correct
23 Correct 223 ms 25280 KB Output is correct
24 Correct 230 ms 32200 KB Output is correct
25 Correct 223 ms 33984 KB Output is correct
26 Correct 212 ms 32256 KB Output is correct
27 Correct 250 ms 31676 KB Output is correct
28 Correct 227 ms 28608 KB Output is correct
29 Correct 275 ms 28528 KB Output is correct
30 Correct 229 ms 26572 KB Output is correct
31 Correct 247 ms 26652 KB Output is correct
32 Correct 244 ms 28244 KB Output is correct
33 Correct 238 ms 26736 KB Output is correct
34 Correct 242 ms 26544 KB Output is correct
35 Correct 226 ms 26164 KB Output is correct