oj.uz

Submission #90864

# Submission time Handle Problem Language Result Execution time Memory
90864 2018-12-25T03:47:18 Z adlet Birthday gift (IZhO18_treearray) C++17
0 / 100
 56 ms 5428 KB 
#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;

typedef long long ll;

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

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 + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
    t[v] = lca(t[v + v], t[v + v + 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 + v, tl, tm, pos, x);
    else
        upd(v + v + 1, tm + 1, tr, pos, x);
    t[v] = lca(t[v + v], t[v + v + 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 + v, tl, tm, l, r);
    int rv = get(v + v + 1, tm + 1, tr, l, r);
    if (lv == -1)
        lv = rv;
    else if (rv == -1)
        rv = lv;
    return lca(lv, rv);
}

int getq(int l, int r) {
    return get(1, 1, n, l, r);
}

int main() {
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int v, u;
        cin >> v >> u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dfs(1);
    for (int i = 1; i <= m; ++i) {
        cin >> x[i];
    }
    build(1, 1, n);
    while (q--) {
        int ll = -1, rr = -1, l, r, type;
        cin >> type >> l >> r;
        if (type == 1) {
            upd(1, 1, n, l, r);
        } else {
            int v;
            cin >> v;
            for (int a = l; a <= r; ++a) {
                for (int b = a; b <= r; ++b) {
                    if (getq(a, b) == v) {
                        ll = a;
                        rr = b;
                        break;
                    }
                }
                if (ll != -1 && rr != -1)
                    break;
            }
            cout << ll << " " << rr << "\n";
        }
    }
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1


*/

Compilation message

treearray.cpp: In function 'int dfs(int, int, int)':
treearray.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
treearray.cpp: In function 'void build(int, int, int)':
treearray.cpp:61: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:72: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:85:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int tm = tl + tr >> 1;
              ~~~^~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 13 ms 5116 KB n=100
3 Correct 11 ms 5160 KB n=100
4 Correct 8 ms 5160 KB n=100
5 Correct 7 ms 5160 KB n=100
6 Correct 56 ms 5176 KB n=100
7 Correct 55 ms 5304 KB n=100
8 Correct 13 ms 5316 KB n=100
9 Correct 12 ms 5316 KB n=100
10 Correct 33 ms 5352 KB n=100
11 Correct 32 ms 5352 KB n=100
12 Correct 7 ms 5352 KB n=100
13 Correct 8 ms 5352 KB n=100
14 Correct 7 ms 5352 KB n=100
15 Correct 7 ms 5352 KB n=100
16 Correct 7 ms 5352 KB n=100
17 Correct 11 ms 5352 KB n=100
18 Correct 9 ms 5428 KB n=100
19 Correct 6 ms 5428 KB n=100
20 Correct 9 ms 5428 KB n=100
21 Correct 8 ms 5428 KB n=100
22 Correct 6 ms 5428 KB n=100
23 Correct 14 ms 5428 KB n=100
24 Correct 15 ms 5428 KB n=100
25 Correct 7 ms 5428 KB n=100
26 Incorrect 5 ms 5428 KB Jury has the answer but participant has not
27 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 13 ms 5116 KB n=100
3 Correct 11 ms 5160 KB n=100
4 Correct 8 ms 5160 KB n=100
5 Correct 7 ms 5160 KB n=100
6 Correct 56 ms 5176 KB n=100
7 Correct 55 ms 5304 KB n=100
8 Correct 13 ms 5316 KB n=100
9 Correct 12 ms 5316 KB n=100
10 Correct 33 ms 5352 KB n=100
11 Correct 32 ms 5352 KB n=100
12 Correct 7 ms 5352 KB n=100
13 Correct 8 ms 5352 KB n=100
14 Correct 7 ms 5352 KB n=100
15 Correct 7 ms 5352 KB n=100
16 Correct 7 ms 5352 KB n=100
17 Correct 11 ms 5352 KB n=100
18 Correct 9 ms 5428 KB n=100
19 Correct 6 ms 5428 KB n=100
20 Correct 9 ms 5428 KB n=100
21 Correct 8 ms 5428 KB n=100
22 Correct 6 ms 5428 KB n=100
23 Correct 14 ms 5428 KB n=100
24 Correct 15 ms 5428 KB n=100
25 Correct 7 ms 5428 KB n=100
26 Incorrect 5 ms 5428 KB Jury has the answer but participant has not
27 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 13 ms 5116 KB n=100
3 Correct 11 ms 5160 KB n=100
4 Correct 8 ms 5160 KB n=100
5 Correct 7 ms 5160 KB n=100
6 Correct 56 ms 5176 KB n=100
7 Correct 55 ms 5304 KB n=100
8 Correct 13 ms 5316 KB n=100
9 Correct 12 ms 5316 KB n=100
10 Correct 33 ms 5352 KB n=100
11 Correct 32 ms 5352 KB n=100
12 Correct 7 ms 5352 KB n=100
13 Correct 8 ms 5352 KB n=100
14 Correct 7 ms 5352 KB n=100
15 Correct 7 ms 5352 KB n=100
16 Correct 7 ms 5352 KB n=100
17 Correct 11 ms 5352 KB n=100
18 Correct 9 ms 5428 KB n=100
19 Correct 6 ms 5428 KB n=100
20 Correct 9 ms 5428 KB n=100
21 Correct 8 ms 5428 KB n=100
22 Correct 6 ms 5428 KB n=100
23 Correct 14 ms 5428 KB n=100
24 Correct 15 ms 5428 KB n=100
25 Correct 7 ms 5428 KB n=100
26 Incorrect 5 ms 5428 KB Jury has the answer but participant has not
27 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 13 ms 5116 KB n=100
3 Correct 11 ms 5160 KB n=100
4 Correct 8 ms 5160 KB n=100
5 Correct 7 ms 5160 KB n=100
6 Correct 56 ms 5176 KB n=100
7 Correct 55 ms 5304 KB n=100
8 Correct 13 ms 5316 KB n=100
9 Correct 12 ms 5316 KB n=100
10 Correct 33 ms 5352 KB n=100
11 Correct 32 ms 5352 KB n=100
12 Correct 7 ms 5352 KB n=100
13 Correct 8 ms 5352 KB n=100
14 Correct 7 ms 5352 KB n=100
15 Correct 7 ms 5352 KB n=100
16 Correct 7 ms 5352 KB n=100
17 Correct 11 ms 5352 KB n=100
18 Correct 9 ms 5428 KB n=100
19 Correct 6 ms 5428 KB n=100
20 Correct 9 ms 5428 KB n=100
21 Correct 8 ms 5428 KB n=100
22 Correct 6 ms 5428 KB n=100
23 Correct 14 ms 5428 KB n=100
24 Correct 15 ms 5428 KB n=100
25 Correct 7 ms 5428 KB n=100
26 Incorrect 5 ms 5428 KB Jury has the answer but participant has not
27 Halted 0 ms 0 KB -