제출 #520435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520435		borgar02	Min-max tree (BOI18_minmaxtree)	C++17	0 / 100	288 ms	103196 KiB

minmaxtree

#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 : 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), 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;
}

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

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: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42