Submission #91014

#	Time	Username	Problem	Language	Result	Execution time	Memory
91014		adlet	Birthday gift (IZhO18_treearray)	C++17	56 / 100	4078 ms	46352 KiB

treearray

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const int lg = log2(2000) + 1;

int n, m, q, timer, t[N * 4], x[N], lvl[N], tin[N], tout[N], used[N], up[N][lg + 5];

vector < int > g[N];

int dfs(int v, int p = 1, int h = 0) {
    used[v] = 1;
    up[v][0] = p;
    tin[v] = ++timer;
    lvl[v] = h;
    for (int i = 1; i <= lg; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to, v, h + 1);
        }
    }
    tout[v] = ++timer;
}

int lca(int a, int b) {
    if (lvl[a] < lvl[b])
        swap(a, b);
    if (tin[b] <= tin[a] && tout[b] >= tout[a])
        return b;
    for (int i = lg; i >= 0; --i) {
        if (lvl[up[a][i]] >= lvl[b]) {
            a = up[a][i];
        }
    }
    if (a == b)
        return a;
    for (int i = lg; i >= 0; --i) {
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

inline void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = x[tl];
        return;
    }
    int tm = tl + tr >> 1;
    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);
    t[v] = lca(t[v << 1], t[v << 1 | 1]);
}

inline void upd(int v, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        t[v] = x;
        return;
    }
    int tm = tl + tr >> 1;
    if (pos <= tm)
        upd(v << 1, tl, tm, pos, x);
    else
        upd(v << 1 | 1, tm + 1, tr, pos, x);
    t[v] = lca(t[v << 1], t[v << 1 | 1]);
}

int get(int v, int tl, int tr, int l, int r) {
    if (tl > r || tr < l)
        return -1;
    if (tl >= l && tr <= r)
        return t[v];
    int tm = tl + tr >> 1;
    int lv = get(v << 1, tl, tm, l, r);
    int rv = get(v << 1 | 1, tm + 1, tr, l, r);
    if (lv == -1)
        lv = rv;
    else if (rv == -1)
        rv = lv;
    return lca(lv, rv);
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i < n; ++i) {
        int v, u;
        scanf("%d%d", &v, &u);
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dfs(1);
    for (int i = 1; i <= m; ++i) {
        scanf("%d", x + i);
    }
    build(1, 1, m);
    while (q--) {
        int ll = -1, rr = -1, a, b, type;
        scanf("%d%d%d", &type, &a, &b);
        if (type == 1) {
            upd(1, 1, m, a, b);
        } else {
            int v;
            cin >> v;
            int l = a, r = a, ll = -1, rr = -1;
            while (l <= b && r <= b) {
                if (l > r)
                    r = l;
                int fnd = get(1, 1, m, l, r);
                if (fnd == v) {
                    ll = l;
                    rr = r;
                    break;
                }
                if (lvl[fnd] < lvl[v])
                    ++l;
                else
                    ++r;
            }
            cout << ll << " " << rr << "\n";
        }
    }
}

Compilation message (stderr)

treearray.cpp: In function 'int dfs(int, int, int)':
treearray.cpp:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
treearray.cpp: In function 'void build(int, int, int)':
treearray.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int tm = tl + tr >> 1;
              ~~~^~~~
treearray.cpp: In function 'void upd(int, int, int, int, int)':
treearray.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int tm = tl + tr >> 1;
              ~~~^~~~
treearray.cpp: In function 'int get(int, int, int, int, int)':
treearray.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int tm = tl + tr >> 1;
              ~~~^~~~
treearray.cpp: In function 'int main()':
treearray.cpp:107:13: warning: unused variable 'll' [-Wunused-variable]
         int ll = -1, rr = -1, a, b, type;
             ^~
treearray.cpp:107:22: warning: unused variable 'rr' [-Wunused-variable]
         int ll = -1, rr = -1, a, b, type;
                      ^~
treearray.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &u);
         ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", x + i);
         ~~~~~^~~~~~~~~~~~~
treearray.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &type, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44