#include <bits/stdc++.h>
using namespace std;
ifstream fin("minmaxtree.in");
ofstream fout("minmaxtree.out");
const int N = 70000, inf = 1e9;
vector <int> g[N + 5], tin, r, e;
int l, timer;
void dfs(int v, int p)
{
tin[v] = ++timer;
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)];
}
set <int> max_node[N + 5], min_node[N + 5], max_erase[N + 5], min_erase[N + 5];
pair <int, int> range[N + 5];
void compute_ranges(int u, int p) {
for(int v : g[u])
if(v != p)
compute_ranges(v, u);
for(int val : min_erase[u]) min_node[u].erase(val);
for(int val : max_erase[u]) max_node[u].erase(val);
int left = min_node[u].size() ? *min_node[u].rbegin() : -inf,
right = max_node[u].size() ? *max_node[u].begin() : inf;
range[u] = make_pair(left, right);
if(min_node[p].size() < min_node[u].size()) swap(min_node[p], min_node[u]);
if(max_node[p].size() < max_node[u].size()) swap(max_node[p], max_node[u]);
for(int val : min_node[u]) min_node[p].insert(val);
for(int val : max_node[u]) max_node[p].insert(val);
}
class Matcher {
int n, m;
vector <vector <int>> g;
vector <int> l, r;
vector <bool> up;
bool pairup(int u) {
if(up[u]) return false;
up[u] = true;
for(int v : g[u]) if(!r[v])
return r[l[u] = v] = u;
for(int v : g[u]) if(pairup(r[v]))
return r[l[u] = v] = u;
return false;
}
public:
Matcher(int _n, int _m) : n(_n), m(_m), g(n + 1), l(n + 1, 0), r(m + 1, 0), up(max(n, m) + 1) {}
void add_edge(int u, int v) { g[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;
void print_sol(int u, int p) {
if(p) fout << u << " " << p << " " << res[u] << "\n";
for(int v : g[u]) if(v != p)
print_sol(v, u);
}
int main()
{
int n, q, x, y, z;
fin >> n;
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;
fin >> q;
for(int i = 1; i <= q; i++) {
char t;
fin >> t >> x >> y >> z;
if(t == 'M') {
max_node[x].insert(z);
max_node[y].insert(z);
max_erase[lca(x, y)].insert(z);
} else {
min_node[x].insert(z);
min_node[y].insert(z);
min_erase[lca(x, y)].insert(z);
}
}
compute_ranges(1, 0);
//for(int i = 1; i <= n; i++) fout << range[i].first << " " << range[i].second << "\n";
map <int, int> compress; vector <int> decompress;
for(int i = 1; i <= n; i++)
compress[range[i].first] = compress[range[i].second] = 1;
int k = 0;
decompress.resize(k + 1, 0);
for(auto& e : compress) {
e.second = ++k;
decompress[k] = e.first;
}
Matcher M(n, k);
for(int i = 1; i <= n; i++) {
if(range[i].first == -inf && range[i].second == inf) M.add_edge(i, compress[inf]);
else {
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 - 1);
for(auto p : sol)
res[p.first] = decompress[p.second];
for(int i = 1; i <= n; i++)
if(res[i] == -inf - 1)
res[i] = range[i].first;
print_sol(1, 0);*/
return 0;
}
Compilation message
minmaxtree.cpp: In member function 'bool Matcher::pairup(int)':
minmaxtree.cpp:76:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
76 | return r[l[u] = v] = u;
minmaxtree.cpp:78:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
78 | return r[l[u] = v] = u;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
122 ms |
217040 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
121 ms |
217028 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
126 ms |
217096 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
122 ms |
217040 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
