oj.uz

Submission #520609

# Submission time Handle Problem Language Result Execution time Memory
520609 2022-01-30T10:33:12 Z borgar02 Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 240 ms 30960 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 + 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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 30148 KB Output is correct
2 Correct 209 ms 28316 KB Output is correct
3 Correct 197 ms 28264 KB Output is correct
4 Correct 213 ms 30960 KB Output is correct
5 Correct 207 ms 28176 KB Output is correct
6 Correct 208 ms 28972 KB Output is correct
7 Correct 204 ms 28244 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 23260 KB Output is correct
2 Correct 139 ms 23788 KB Output is correct
3 Correct 122 ms 24888 KB Output is correct
4 Correct 121 ms 25736 KB Output is correct
5 Correct 147 ms 24412 KB Output is correct
6 Correct 137 ms 24940 KB Output is correct
7 Correct 156 ms 24448 KB Output is correct
8 Correct 135 ms 24376 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 238 ms 30148 KB Output is correct
6 Correct 209 ms 28316 KB Output is correct
7 Correct 197 ms 28264 KB Output is correct
8 Correct 213 ms 30960 KB Output is correct
9 Correct 207 ms 28176 KB Output is correct
10 Correct 208 ms 28972 KB Output is correct
11 Correct 204 ms 28244 KB Output is correct
12 Correct 130 ms 23260 KB Output is correct
13 Correct 139 ms 23788 KB Output is correct
14 Correct 122 ms 24888 KB Output is correct
15 Correct 121 ms 25736 KB Output is correct
16 Correct 147 ms 24412 KB Output is correct
17 Correct 137 ms 24940 KB Output is correct
18 Correct 156 ms 24448 KB Output is correct
19 Correct 135 ms 24376 KB Output is correct
20 Correct 223 ms 27768 KB Output is correct
21 Correct 186 ms 26492 KB Output is correct
22 Correct 182 ms 26660 KB Output is correct
23 Correct 186 ms 26848 KB Output is correct
24 Correct 221 ms 29804 KB Output is correct
25 Correct 220 ms 30900 KB Output is correct
26 Correct 225 ms 30500 KB Output is correct
27 Correct 240 ms 29356 KB Output is correct
28 Correct 233 ms 28216 KB Output is correct
29 Correct 238 ms 28284 KB Output is correct
30 Correct 229 ms 27044 KB Output is correct
31 Correct 198 ms 27268 KB Output is correct
32 Correct 219 ms 27948 KB Output is correct
33 Correct 238 ms 27484 KB Output is correct
34 Correct 206 ms 27528 KB Output is correct
35 Correct 197 ms 27064 KB Output is correct