Submission #520609

#	Time	Username	Problem	Language	Result	Execution time	Memory
520609		borgar02	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	240 ms	30960 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 + 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)
      |           ^

• Subtask 1: 7 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42