oj.uz

Submission #91014

# Submission time Handle Problem Language Result Execution time Memory
91014 2018-12-25T15:24:25 Z adlet Birthday gift (IZhO18_treearray) C++17
56 / 100
 4000 ms 46352 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;

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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB n=5
2 Correct 5 ms 5108 KB n=100
3 Correct 7 ms 5184 KB n=100
4 Correct 5 ms 5204 KB n=100
5 Correct 5 ms 5248 KB n=100
6 Correct 6 ms 5248 KB n=100
7 Correct 6 ms 5248 KB n=100
8 Correct 7 ms 5324 KB n=100
9 Correct 6 ms 5324 KB n=100
10 Correct 7 ms 5324 KB n=100
11 Correct 7 ms 5356 KB n=100
12 Correct 6 ms 5356 KB n=100
13 Correct 7 ms 5364 KB n=100
14 Correct 6 ms 5368 KB n=100
15 Correct 5 ms 5368 KB n=100
16 Correct 5 ms 5368 KB n=100
17 Correct 7 ms 5368 KB n=100
18 Correct 6 ms 5380 KB n=100
19 Correct 5 ms 5380 KB n=100
20 Correct 6 ms 5384 KB n=100
21 Correct 7 ms 5388 KB n=100
22 Correct 6 ms 5392 KB n=100
23 Correct 7 ms 5392 KB n=100
24 Correct 7 ms 5400 KB n=100
25 Correct 6 ms 5404 KB n=100
26 Correct 6 ms 5404 KB n=12
27 Correct 7 ms 5404 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB n=5
2 Correct 5 ms 5108 KB n=100
3 Correct 7 ms 5184 KB n=100
4 Correct 5 ms 5204 KB n=100
5 Correct 5 ms 5248 KB n=100
6 Correct 6 ms 5248 KB n=100
7 Correct 6 ms 5248 KB n=100
8 Correct 7 ms 5324 KB n=100
9 Correct 6 ms 5324 KB n=100
10 Correct 7 ms 5324 KB n=100
11 Correct 7 ms 5356 KB n=100
12 Correct 6 ms 5356 KB n=100
13 Correct 7 ms 5364 KB n=100
14 Correct 6 ms 5368 KB n=100
15 Correct 5 ms 5368 KB n=100
16 Correct 5 ms 5368 KB n=100
17 Correct 7 ms 5368 KB n=100
18 Correct 6 ms 5380 KB n=100
19 Correct 5 ms 5380 KB n=100
20 Correct 6 ms 5384 KB n=100
21 Correct 7 ms 5388 KB n=100
22 Correct 6 ms 5392 KB n=100
23 Correct 7 ms 5392 KB n=100
24 Correct 7 ms 5400 KB n=100
25 Correct 6 ms 5404 KB n=100
26 Correct 6 ms 5404 KB n=12
27 Correct 7 ms 5404 KB n=100
28 Correct 7 ms 5408 KB n=500
29 Correct 11 ms 5420 KB n=500
30 Correct 11 ms 5420 KB n=500
31 Correct 11 ms 5452 KB n=500
32 Correct 7 ms 5468 KB n=500
33 Correct 9 ms 5476 KB n=500
34 Correct 6 ms 5480 KB n=500
35 Correct 9 ms 5492 KB n=500
36 Correct 31 ms 5508 KB n=500
37 Correct 30 ms 5508 KB n=500
38 Correct 31 ms 5516 KB n=500
39 Correct 20 ms 5528 KB n=500
40 Correct 18 ms 5544 KB n=500
41 Correct 18 ms 5560 KB n=500
42 Correct 18 ms 5576 KB n=500
43 Correct 18 ms 5588 KB n=500
44 Correct 18 ms 5604 KB n=500
45 Correct 7 ms 5616 KB n=500
46 Correct 11 ms 5628 KB n=500
47 Correct 23 ms 5640 KB n=500
48 Correct 6 ms 5656 KB n=500
49 Correct 9 ms 5668 KB n=500
50 Correct 14 ms 5684 KB n=500
51 Correct 12 ms 5696 KB n=500
52 Correct 13 ms 5712 KB n=500
53 Correct 12 ms 5728 KB n=500
54 Correct 10 ms 5744 KB n=500
55 Correct 7 ms 5756 KB n=278
56 Correct 19 ms 5764 KB n=500
57 Correct 19 ms 5776 KB n=500
58 Correct 20 ms 5848 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB n=5
2 Correct 5 ms 5108 KB n=100
3 Correct 7 ms 5184 KB n=100
4 Correct 5 ms 5204 KB n=100
5 Correct 5 ms 5248 KB n=100
6 Correct 6 ms 5248 KB n=100
7 Correct 6 ms 5248 KB n=100
8 Correct 7 ms 5324 KB n=100
9 Correct 6 ms 5324 KB n=100
10 Correct 7 ms 5324 KB n=100
11 Correct 7 ms 5356 KB n=100
12 Correct 6 ms 5356 KB n=100
13 Correct 7 ms 5364 KB n=100
14 Correct 6 ms 5368 KB n=100
15 Correct 5 ms 5368 KB n=100
16 Correct 5 ms 5368 KB n=100
17 Correct 7 ms 5368 KB n=100
18 Correct 6 ms 5380 KB n=100
19 Correct 5 ms 5380 KB n=100
20 Correct 6 ms 5384 KB n=100
21 Correct 7 ms 5388 KB n=100
22 Correct 6 ms 5392 KB n=100
23 Correct 7 ms 5392 KB n=100
24 Correct 7 ms 5400 KB n=100
25 Correct 6 ms 5404 KB n=100
26 Correct 6 ms 5404 KB n=12
27 Correct 7 ms 5404 KB n=100
28 Correct 7 ms 5408 KB n=500
29 Correct 11 ms 5420 KB n=500
30 Correct 11 ms 5420 KB n=500
31 Correct 11 ms 5452 KB n=500
32 Correct 7 ms 5468 KB n=500
33 Correct 9 ms 5476 KB n=500
34 Correct 6 ms 5480 KB n=500
35 Correct 9 ms 5492 KB n=500
36 Correct 31 ms 5508 KB n=500
37 Correct 30 ms 5508 KB n=500
38 Correct 31 ms 5516 KB n=500
39 Correct 20 ms 5528 KB n=500
40 Correct 18 ms 5544 KB n=500
41 Correct 18 ms 5560 KB n=500
42 Correct 18 ms 5576 KB n=500
43 Correct 18 ms 5588 KB n=500
44 Correct 18 ms 5604 KB n=500
45 Correct 7 ms 5616 KB n=500
46 Correct 11 ms 5628 KB n=500
47 Correct 23 ms 5640 KB n=500
48 Correct 6 ms 5656 KB n=500
49 Correct 9 ms 5668 KB n=500
50 Correct 14 ms 5684 KB n=500
51 Correct 12 ms 5696 KB n=500
52 Correct 13 ms 5712 KB n=500
53 Correct 12 ms 5728 KB n=500
54 Correct 10 ms 5744 KB n=500
55 Correct 7 ms 5756 KB n=278
56 Correct 19 ms 5764 KB n=500
57 Correct 19 ms 5776 KB n=500
58 Correct 20 ms 5848 KB n=500
59 Correct 10 ms 5932 KB n=2000
60 Correct 76 ms 6188 KB n=2000
61 Correct 72 ms 6228 KB n=2000
62 Correct 55 ms 6228 KB n=2000
63 Correct 11 ms 6252 KB n=2000
64 Correct 69 ms 6304 KB n=2000
65 Correct 11 ms 6360 KB n=2000
66 Correct 82 ms 6524 KB n=2000
67 Correct 14 ms 6524 KB n=2000
68 Correct 70 ms 6628 KB n=2000
69 Correct 530 ms 6660 KB n=2000
70 Correct 529 ms 6712 KB n=2000
71 Correct 531 ms 6844 KB n=2000
72 Correct 269 ms 6844 KB n=2000
73 Correct 267 ms 6872 KB n=2000
74 Correct 9 ms 6880 KB n=1844
75 Correct 277 ms 7052 KB n=2000
76 Correct 273 ms 7052 KB n=2000
77 Correct 277 ms 7052 KB n=2000
78 Correct 285 ms 7084 KB n=2000
79 Correct 9 ms 7104 KB n=2000
80 Correct 66 ms 7184 KB n=2000
81 Correct 62 ms 7240 KB n=2000
82 Correct 10 ms 7296 KB n=2000
83 Correct 66 ms 7436 KB n=2000
84 Correct 136 ms 7448 KB n=2000
85 Correct 106 ms 7456 KB n=2000
86 Correct 108 ms 7508 KB n=2000
87 Correct 134 ms 7604 KB n=2000
88 Correct 267 ms 7732 KB n=2000
89 Correct 263 ms 7784 KB n=2000
90 Correct 89 ms 7784 KB n=2000
91 Correct 364 ms 7784 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB n=5
2 Correct 5 ms 5108 KB n=100
3 Correct 7 ms 5184 KB n=100
4 Correct 5 ms 5204 KB n=100
5 Correct 5 ms 5248 KB n=100
6 Correct 6 ms 5248 KB n=100
7 Correct 6 ms 5248 KB n=100
8 Correct 7 ms 5324 KB n=100
9 Correct 6 ms 5324 KB n=100
10 Correct 7 ms 5324 KB n=100
11 Correct 7 ms 5356 KB n=100
12 Correct 6 ms 5356 KB n=100
13 Correct 7 ms 5364 KB n=100
14 Correct 6 ms 5368 KB n=100
15 Correct 5 ms 5368 KB n=100
16 Correct 5 ms 5368 KB n=100
17 Correct 7 ms 5368 KB n=100
18 Correct 6 ms 5380 KB n=100
19 Correct 5 ms 5380 KB n=100
20 Correct 6 ms 5384 KB n=100
21 Correct 7 ms 5388 KB n=100
22 Correct 6 ms 5392 KB n=100
23 Correct 7 ms 5392 KB n=100
24 Correct 7 ms 5400 KB n=100
25 Correct 6 ms 5404 KB n=100
26 Correct 6 ms 5404 KB n=12
27 Correct 7 ms 5404 KB n=100
28 Correct 7 ms 5408 KB n=500
29 Correct 11 ms 5420 KB n=500
30 Correct 11 ms 5420 KB n=500
31 Correct 11 ms 5452 KB n=500
32 Correct 7 ms 5468 KB n=500
33 Correct 9 ms 5476 KB n=500
34 Correct 6 ms 5480 KB n=500
35 Correct 9 ms 5492 KB n=500
36 Correct 31 ms 5508 KB n=500
37 Correct 30 ms 5508 KB n=500
38 Correct 31 ms 5516 KB n=500
39 Correct 20 ms 5528 KB n=500
40 Correct 18 ms 5544 KB n=500
41 Correct 18 ms 5560 KB n=500
42 Correct 18 ms 5576 KB n=500
43 Correct 18 ms 5588 KB n=500
44 Correct 18 ms 5604 KB n=500
45 Correct 7 ms 5616 KB n=500
46 Correct 11 ms 5628 KB n=500
47 Correct 23 ms 5640 KB n=500
48 Correct 6 ms 5656 KB n=500
49 Correct 9 ms 5668 KB n=500
50 Correct 14 ms 5684 KB n=500
51 Correct 12 ms 5696 KB n=500
52 Correct 13 ms 5712 KB n=500
53 Correct 12 ms 5728 KB n=500
54 Correct 10 ms 5744 KB n=500
55 Correct 7 ms 5756 KB n=278
56 Correct 19 ms 5764 KB n=500
57 Correct 19 ms 5776 KB n=500
58 Correct 20 ms 5848 KB n=500
59 Correct 10 ms 5932 KB n=2000
60 Correct 76 ms 6188 KB n=2000
61 Correct 72 ms 6228 KB n=2000
62 Correct 55 ms 6228 KB n=2000
63 Correct 11 ms 6252 KB n=2000
64 Correct 69 ms 6304 KB n=2000
65 Correct 11 ms 6360 KB n=2000
66 Correct 82 ms 6524 KB n=2000
67 Correct 14 ms 6524 KB n=2000
68 Correct 70 ms 6628 KB n=2000
69 Correct 530 ms 6660 KB n=2000
70 Correct 529 ms 6712 KB n=2000
71 Correct 531 ms 6844 KB n=2000
72 Correct 269 ms 6844 KB n=2000
73 Correct 267 ms 6872 KB n=2000
74 Correct 9 ms 6880 KB n=1844
75 Correct 277 ms 7052 KB n=2000
76 Correct 273 ms 7052 KB n=2000
77 Correct 277 ms 7052 KB n=2000
78 Correct 285 ms 7084 KB n=2000
79 Correct 9 ms 7104 KB n=2000
80 Correct 66 ms 7184 KB n=2000
81 Correct 62 ms 7240 KB n=2000
82 Correct 10 ms 7296 KB n=2000
83 Correct 66 ms 7436 KB n=2000
84 Correct 136 ms 7448 KB n=2000
85 Correct 106 ms 7456 KB n=2000
86 Correct 108 ms 7508 KB n=2000
87 Correct 134 ms 7604 KB n=2000
88 Correct 267 ms 7732 KB n=2000
89 Correct 263 ms 7784 KB n=2000
90 Correct 89 ms 7784 KB n=2000
91 Correct 364 ms 7784 KB n=2000
92 Correct 1823 ms 40028 KB n=200000
93 Execution timed out 4078 ms 46352 KB Time limit exceeded
94 Halted 0 ms 0 KB -