제출 #893983

#제출 시각아이디문제언어결과실행 시간메모리
893983azosiMin-max tree (BOI18_minmaxtree)C++17
29 / 100
205 ms31184 KiB
#include <bits/stdc++.h> 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); } vector<int> bench[70707]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; 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; } vector<int> zz; 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); zz.push_back(c); } sort(zz.begin(), zz.end()); zz.resize(unique(zz.begin(), zz.end()) - zz.begin()); memset(mx, -1, sizeof(mx)); memset(mn, -1, sizeof(mn)); for (int i = 2; i <= n; i++) { int maxi = querymax(1, 1, n, in[i], in[i]); int mini = querymin(1, 1, n, in[i], in[i]); if (mini != inf) { mn[i] = lower_bound(zz.begin(), zz.end(), mini) - zz.begin(); bench[mn[i]].push_back(i); } if (maxi != -inf) { mx[i] = lower_bound(zz.begin(), zz.end(), maxi) - zz.begin(); bench[mx[i]].push_back(i); } } set<pair<int, int>> s; for (int i = 0; i < zz.size(); ++i) { cnt[i] = bench[i].size(); s.insert({bench[i].size(), i}); } for (auto &i: ans) i = inf; while (!s.empty()) { int id = s.begin()->second; s.erase(s.begin()); chk[id] = 1; int v = 0; for (auto node: bench[id]) if (ans[node] == inf) { v = node; break; } if (mn[v] != -1 && !chk[mn[v]]) { s.erase({cnt[mn[v]], mn[v]}); cnt[mn[v]]--; s.insert({cnt[mn[v]], mn[v]}); } if (mx[v] != -1 && !chk[mx[v]]) { s.erase({cnt[mx[v]], mx[v]}); cnt[mx[v]]--; s.insert({cnt[mx[v]], mx[v]}); } ans[v] = zz[id]; } for (int i = 2; i <= n; ++i) { cout << i << ' ' << par[i] << ' '; if (ans[i] != inf) cout << ans[i]; else { if (mn[i] != -1) { cout << zz[mn[i]]; } else { cout << 0; } } cout << '\n'; } }

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

minmaxtree.cpp: In function 'void updatemin(int, int, int, int, int, int)':
minmaxtree.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int m = s + e >> 1;
      |             ~~^~~
minmaxtree.cpp: In function 'void updatemax(int, int, int, int, int, int)':
minmaxtree.cpp:79:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int m = s + e >> 1;
      |             ~~^~~
minmaxtree.cpp: In function 'int querymin(int, int, int, int, int)':
minmaxtree.cpp:89:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     int m = s + e >> 1;
      |             ~~^~~
minmaxtree.cpp: In function 'int querymax(int, int, int, int, int)':
minmaxtree.cpp:99:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     int m = s + e >> 1;
      |             ~~^~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:200:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |     for (int i = 0; i < zz.size(); ++i) {
      |                     ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...