oj.uz

Submission #520608

# Submission time Handle Problem Language Result Execution time Memory
520608 2022-01-30T10:31:08 Z borgar02 Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 382 ms 57920 KB 
#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;
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 <int> gg[N + 5];
    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), 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;

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(1, 0);
    for(int i = 1; i <= n; i++)
        compress[range[i].first] = compress[range[i].second] = 1;
    int k = 0;
    for(auto& e : compress) {
        e.second = ++k;
        decompress.push_back(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:81:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   81 |             return r[l[u] = v] = u;
minmaxtree.cpp:83:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   83 |             return r[l[u] = v] = u;

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16716 KB Output is correct
2 Correct 9 ms 16720 KB Output is correct
3 Correct 8 ms 16748 KB Output is correct
4 Correct 8 ms 16720 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 53252 KB Output is correct
2 Correct 338 ms 55484 KB Output is correct
3 Correct 278 ms 51520 KB Output is correct
4 Correct 307 ms 56280 KB Output is correct
5 Correct 305 ms 53340 KB Output is correct
6 Correct 306 ms 52060 KB Output is correct
7 Correct 316 ms 47296 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 38752 KB Output is correct
2 Correct 174 ms 40448 KB Output is correct
3 Correct 171 ms 43220 KB Output is correct
4 Correct 166 ms 45336 KB Output is correct
5 Correct 197 ms 41396 KB Output is correct
6 Correct 204 ms 42420 KB Output is correct
7 Correct 199 ms 40984 KB Output is correct
8 Correct 199 ms 40880 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16716 KB Output is correct
2 Correct 9 ms 16720 KB Output is correct
3 Correct 8 ms 16748 KB Output is correct
4 Correct 8 ms 16720 KB Output is correct
5 Correct 300 ms 53252 KB Output is correct
6 Correct 338 ms 55484 KB Output is correct
7 Correct 278 ms 51520 KB Output is correct
8 Correct 307 ms 56280 KB Output is correct
9 Correct 305 ms 53340 KB Output is correct
10 Correct 306 ms 52060 KB Output is correct
11 Correct 316 ms 47296 KB Output is correct
12 Correct 172 ms 38752 KB Output is correct
13 Correct 174 ms 40448 KB Output is correct
14 Correct 171 ms 43220 KB Output is correct
15 Correct 166 ms 45336 KB Output is correct
16 Correct 197 ms 41396 KB Output is correct
17 Correct 204 ms 42420 KB Output is correct
18 Correct 199 ms 40984 KB Output is correct
19 Correct 199 ms 40880 KB Output is correct
20 Correct 382 ms 56508 KB Output is correct
21 Correct 302 ms 54112 KB Output is correct
22 Correct 329 ms 55780 KB Output is correct
23 Correct 314 ms 53732 KB Output is correct
24 Correct 322 ms 55356 KB Output is correct
25 Correct 375 ms 57920 KB Output is correct
26 Correct 331 ms 55360 KB Output is correct
27 Correct 348 ms 55128 KB Output is correct
28 Correct 314 ms 52048 KB Output is correct
29 Correct 328 ms 52420 KB Output is correct
30 Correct 303 ms 50432 KB Output is correct
31 Correct 305 ms 51324 KB Output is correct
32 Correct 340 ms 52316 KB Output is correct
33 Correct 356 ms 53332 KB Output is correct
34 Correct 348 ms 53376 KB Output is correct
35 Correct 316 ms 50244 KB Output is correct