Submission #520609

#TimeUsernameProblemLanguageResultExecution timeMemory
520609borgar02Min-max tree (BOI18_minmaxtree)C++17
100 / 100
240 ms30960 KiB
#include <bits/stdc++.h> using namespace std; #ifdef INFOARENA ifstream fin("minmaxtree.in"); ofstream fout("minmaxtree.out"); #else #define fin cin #define fout cout #endif const int N = 70000, inf = 1e9 + 1; vector <int> g[N + 5], tin, r, e; int path[N + 5], par[N + 5], depth[N + 5]; int timer; void dfs(int v, int p) { tin[v] = ++timer; par[v] = p; path[v] = p; depth[v] = depth[p] + 1; r[timer] = v; e[timer] = timer; for(int u : g[v]) if(u != p) dfs(u, v); e[++timer] = tin[p]; } template <typename T> class RMQ { vector <int> lg2; vector <vector <T>> dp; int n, h; function <T(T, T)> f; public: template <typename Iterator> RMQ(Iterator op, Iterator ed, function <T(T, T)> _f) : n(ed - op), f(_f) { h = (31 - __builtin_clz(n)); lg2.resize(n + 1, 0); dp.resize(h + 1); for(int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1; dp[0].resize(n); int i = 0; for(Iterator it = op; it != ed; it++, i++) dp[0][i] = *it; for(int j = 1; j <= h; j++) { int jj = (1 << (j - 1)), nj = n - (1 << j); dp[j].resize(nj + 1); for(int i = 0; i <= nj; i++) dp[j][i] = f(dp[j - 1][i], dp[j - 1][i + jj]); } } T query(int l, int r) { /// indexat de la 0 pe intervalul [l, r) int hh = lg2[r - l]; return f(dp[hh][l], dp[hh][r - (1 << hh)]); } }; RMQ <int>* LCA; int lca(int u, int v) { u = tin[u]; v = tin[v]; if(u > v) swap(u, v); return r[LCA -> query(u, v + 1)]; } struct Query { char type; int u, v, val; Query() {} Query(char _type, int _u, int _v, int _val) : type(_type), u(_u), v(_v), val(_val) {} friend inline bool operator <(const Query& a, const Query& b) { return a.val < b.val; } friend inline bool operator >(const Query& a, const Query& b) { return a.val > b.val; } }; vector <Query> qmin, qmax; pair <int, int> range[N + 5]; class Matcher { int n, m; vector <vector <int>> gg; vector <int> l, r; vector <bool> up; bool pairup(int u) { if(up[u]) return false; up[u] = true; for(int v : gg[u]) if(!r[v]) return r[l[u] = v] = u; for(int v : gg[u]) if(pairup(r[v])) return r[l[u] = v] = u; return false; } public: Matcher(int _n, int _m) : n(_n), m(_m), l(_n + 1, 0), r(_m + 1, 0), gg(_n + 1, vector <int>(0)), up(max(_n, _m) + 1) {} void add_edge(int u, int v) { gg[u].push_back(v); } vector <pair <int, int>> match() { for(bool ok = true; ok; ) { fill(up.begin(), up.end(), false); ok = false; for(int i = 1; i <= n; i++) if(!l[i]) ok |= pairup(i); } vector <pair <int, int>> sol; for(int i = 1; i <= n; i++) if(l[i] > 0) sol.emplace_back(i, l[i]); return sol; } }; vector <int> res; int main() { map <int, int> compress; vector <int> decompress; int n, q, x, y, z; fin >> n; decompress.resize(n + 1); tin.resize(n + 1); r.resize(2 * n + 1); e.resize(2 * n + 1); for(int i = 1; i < n; i++) fin >> x >> y, g[x].push_back(y), g[y].push_back(x); dfs(1, 0); RMQ <int> rmq(e.begin(), e.end(), [](int a, int b){ return min(a, b); }); LCA = &rmq; fill(range + 1, range + n + 1, make_pair(-inf, inf)); fin >> q; for(int i = 1; i <= q; i++) { char t; fin >> t >> x >> y >> z; compress[z] = i; decompress[i] = z; if(t == 'M') { qmax.emplace_back(t, x, y, z); } else { qmin.emplace_back(t, x, y, z); } } sort(qmin.rbegin(), qmin.rend()); sort(qmax.begin(), qmax.end()); for(Query q : qmin) { int _lca = lca(q.u, q.v); for(int node : {q.u, q.v}) while(depth[node] > depth[_lca]) { if(range[node].first == -inf) range[node].first = q.val; int nodecopy = node; node = path[node]; path[nodecopy] = _lca; } } for(int i = 1; i <= n; i++) path[i] = par[i]; for(Query q : qmax) { int _lca = lca(q.u, q.v); for(int node : {q.u, q.v}) while(depth[node] > depth[_lca]) { if(range[node].second == inf) range[node].second = q.val; int nodecopy = node; node = path[node]; path[nodecopy] = _lca; } } Matcher M(n, q); for(int i = 2; i <= n; i++) { if(range[i].first != -inf) M.add_edge(i, compress[range[i].first]); if(range[i].second != inf) M.add_edge(i, compress[range[i].second]); } vector <pair <int, int>> sol = M.match(); res.resize(n + 1, -inf); for(auto p : sol) res[p.first] = decompress[p.second]; for(int i = 1; i <= n; i++) if(res[i] == -inf) if(range[i].first == -inf && range[i].second == inf) res[i] = 0; else if(range[i].first == -inf) res[i] = range[i].second; else res[i] = range[i].first; for(int i = 2; i <= n; i++) fout << i << " " << par[i] << " " << res[i] << "\n"; return 0; }

Compilation message (stderr)

minmaxtree.cpp: In member function 'bool Matcher::pairup(int)':
minmaxtree.cpp:79:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   79 |             return r[l[u] = v] = u;
minmaxtree.cpp:81:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   81 |             return r[l[u] = v] = u;
minmaxtree.cpp: In constructor 'Matcher::Matcher(int, int)':
minmaxtree.cpp:73:21: warning: 'Matcher::r' will be initialized after [-Wreorder]
   73 |     vector <int> l, r;
      |                     ^
minmaxtree.cpp:72:27: warning:   'std::vector<std::vector<int>, std::allocator<std::vector<int> > > Matcher::gg' [-Wreorder]
   72 |     vector <vector <int>> gg;
      |                           ^~
minmaxtree.cpp:85:5: warning:   when initialized here [-Wreorder]
   85 |     Matcher(int _n, int _m) : n(_n), m(_m), l(_n + 1, 0), r(_m + 1, 0), gg(_n + 1, vector <int>(0)), up(max(_n, _m) + 1) {}
      |     ^~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:160:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  160 |         if(res[i] == -inf)
      |           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...