oj.uz

답안 #249685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249685 2020-07-15T14:29:54 Z apostoldaniel854 Birthday gift (IZhO18_treearray) C++14
100 / 100
 1872 ms 84036 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int N = 2e5, LG = 20;
int p[LG][1 + N];
int d[1 + N], a[1 + N];
vector <int> gr[1 + N];

int n, m, q;

void dfs (int node, int par) {
    d[node] = d[par] + 1;
    p[0][node] = par;
    for (int son : gr[node])
        if (par != son)
            dfs (son, node);
}

void lift () {
    for (int k = 1; k < LG; k++)
        for (int node = 1; node <= n; node++)
            p[k][node] = p[k - 1][p[k - 1][node]];
}

int lca (int a, int b) {
    int k;
    k = LG - 1;
    while (d[a] > d[b]) {
        if (d[p[k][a]] >= d[b])
            a = p[k][a];
        k--;
    }
    k = LG - 1;
    while (d[a] < d[b]) {
        if (d[p[k][b]] >= d[a])
            b = p[k][b];
        k--;
    }
    k = LG - 1;
    while (k >= 0) {
        if (p[k][a] != p[k][b])
            a = p[k][a], b = p[k][b];
        k--;
    }
    if (a != b)
        a = p[0][a];
    return a;
}

multiset <int> simple[1 + N];
multiset <int> two[1 + N];

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        gr[x].pb (y);
        gr[y].pb (x);
    }

    dfs (1, 0);
    lift ();

    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        simple[a[i]].insert (i);
    }
    for (int i = 1; i < m; i++)
        two[lca (a[i], a[i + 1])].insert (i);
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, value;
            cin >> pos >> value;
            simple[a[pos]].erase (pos);
            if (pos > 1)
                two[lca (a[pos], a[pos - 1])].erase (pos - 1);
            if (pos < m)
                two[lca (a[pos], a[pos + 1])].erase (pos);

            a[pos] = value;
            simple[a[pos]].insert (pos);
            if (pos > 1)
                two[lca (a[pos], a[pos - 1])].insert (pos - 1);
            if (pos < m)
                two[lca (a[pos], a[pos + 1])].insert (pos);
        }
        else {
            int l, r, value;
            cin >> l >> r >> value;
            auto it = simple[value].lower_bound (l);
            if (it != simple[value].end () && *it <= r)
                cout << *it << " " << *it << "\n";
            else {
                it = two[value].lower_bound (l);
                if (it != two[value].end () && *it < r)
                    cout << *it << " " << *it + 1 << "\n";
                else
                    cout << "-1 -1\n";
            }
        }
    }
    return 0;
}
/**
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
**/

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23936 KB n=5
2 Correct 17 ms 23936 KB n=100
3 Correct 14 ms 23936 KB n=100
4 Correct 16 ms 23968 KB n=100
5 Correct 15 ms 23936 KB n=100
6 Correct 14 ms 23936 KB n=100
7 Correct 17 ms 23936 KB n=100
8 Correct 17 ms 23936 KB n=100
9 Correct 16 ms 23936 KB n=100
10 Correct 14 ms 23936 KB n=100
11 Correct 19 ms 23936 KB n=100
12 Correct 15 ms 23936 KB n=100
13 Correct 14 ms 23936 KB n=100
14 Correct 14 ms 23936 KB n=100
15 Correct 17 ms 23936 KB n=100
16 Correct 16 ms 23936 KB n=100
17 Correct 19 ms 23936 KB n=100
18 Correct 15 ms 23936 KB n=100
19 Correct 15 ms 23936 KB n=100
20 Correct 14 ms 23936 KB n=100
21 Correct 19 ms 23936 KB n=100
22 Correct 17 ms 23936 KB n=100
23 Correct 14 ms 23936 KB n=100
24 Correct 16 ms 23912 KB n=100
25 Correct 20 ms 23936 KB n=100
26 Correct 14 ms 23936 KB n=12
27 Correct 14 ms 23936 KB n=100

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23936 KB n=5
2 Correct 17 ms 23936 KB n=100
3 Correct 14 ms 23936 KB n=100
4 Correct 16 ms 23968 KB n=100
5 Correct 15 ms 23936 KB n=100
6 Correct 14 ms 23936 KB n=100
7 Correct 17 ms 23936 KB n=100
8 Correct 17 ms 23936 KB n=100
9 Correct 16 ms 23936 KB n=100
10 Correct 14 ms 23936 KB n=100
11 Correct 19 ms 23936 KB n=100
12 Correct 15 ms 23936 KB n=100
13 Correct 14 ms 23936 KB n=100
14 Correct 14 ms 23936 KB n=100
15 Correct 17 ms 23936 KB n=100
16 Correct 16 ms 23936 KB n=100
17 Correct 19 ms 23936 KB n=100
18 Correct 15 ms 23936 KB n=100
19 Correct 15 ms 23936 KB n=100
20 Correct 14 ms 23936 KB n=100
21 Correct 19 ms 23936 KB n=100
22 Correct 17 ms 23936 KB n=100
23 Correct 14 ms 23936 KB n=100
24 Correct 16 ms 23912 KB n=100
25 Correct 20 ms 23936 KB n=100
26 Correct 14 ms 23936 KB n=12
27 Correct 14 ms 23936 KB n=100
28 Correct 14 ms 24064 KB n=500
29 Correct 15 ms 24040 KB n=500
30 Correct 21 ms 24064 KB n=500
31 Correct 15 ms 24064 KB n=500
32 Correct 15 ms 24056 KB n=500
33 Correct 14 ms 24064 KB n=500
34 Correct 14 ms 24064 KB n=500
35 Correct 15 ms 24064 KB n=500
36 Correct 14 ms 24064 KB n=500
37 Correct 15 ms 24064 KB n=500
38 Correct 14 ms 24064 KB n=500
39 Correct 17 ms 24064 KB n=500
40 Correct 14 ms 24064 KB n=500
41 Correct 18 ms 24064 KB n=500
42 Correct 16 ms 24064 KB n=500
43 Correct 15 ms 24064 KB n=500
44 Correct 15 ms 24064 KB n=500
45 Correct 14 ms 24064 KB n=500
46 Correct 15 ms 24064 KB n=500
47 Correct 18 ms 24064 KB n=500
48 Correct 18 ms 24064 KB n=500
49 Correct 14 ms 24064 KB n=500
50 Correct 16 ms 24064 KB n=500
51 Correct 15 ms 24064 KB n=500
52 Correct 16 ms 24064 KB n=500
53 Correct 16 ms 24044 KB n=500
54 Correct 14 ms 24040 KB n=500
55 Correct 14 ms 24064 KB n=278
56 Correct 19 ms 24064 KB n=500
57 Correct 15 ms 24064 KB n=500
58 Correct 14 ms 24064 KB n=500

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23936 KB n=5
2 Correct 17 ms 23936 KB n=100
3 Correct 14 ms 23936 KB n=100
4 Correct 16 ms 23968 KB n=100
5 Correct 15 ms 23936 KB n=100
6 Correct 14 ms 23936 KB n=100
7 Correct 17 ms 23936 KB n=100
8 Correct 17 ms 23936 KB n=100
9 Correct 16 ms 23936 KB n=100
10 Correct 14 ms 23936 KB n=100
11 Correct 19 ms 23936 KB n=100
12 Correct 15 ms 23936 KB n=100
13 Correct 14 ms 23936 KB n=100
14 Correct 14 ms 23936 KB n=100
15 Correct 17 ms 23936 KB n=100
16 Correct 16 ms 23936 KB n=100
17 Correct 19 ms 23936 KB n=100
18 Correct 15 ms 23936 KB n=100
19 Correct 15 ms 23936 KB n=100
20 Correct 14 ms 23936 KB n=100
21 Correct 19 ms 23936 KB n=100
22 Correct 17 ms 23936 KB n=100
23 Correct 14 ms 23936 KB n=100
24 Correct 16 ms 23912 KB n=100
25 Correct 20 ms 23936 KB n=100
26 Correct 14 ms 23936 KB n=12
27 Correct 14 ms 23936 KB n=100
28 Correct 14 ms 24064 KB n=500
29 Correct 15 ms 24040 KB n=500
30 Correct 21 ms 24064 KB n=500
31 Correct 15 ms 24064 KB n=500
32 Correct 15 ms 24056 KB n=500
33 Correct 14 ms 24064 KB n=500
34 Correct 14 ms 24064 KB n=500
35 Correct 15 ms 24064 KB n=500
36 Correct 14 ms 24064 KB n=500
37 Correct 15 ms 24064 KB n=500
38 Correct 14 ms 24064 KB n=500
39 Correct 17 ms 24064 KB n=500
40 Correct 14 ms 24064 KB n=500
41 Correct 18 ms 24064 KB n=500
42 Correct 16 ms 24064 KB n=500
43 Correct 15 ms 24064 KB n=500
44 Correct 15 ms 24064 KB n=500
45 Correct 14 ms 24064 KB n=500
46 Correct 15 ms 24064 KB n=500
47 Correct 18 ms 24064 KB n=500
48 Correct 18 ms 24064 KB n=500
49 Correct 14 ms 24064 KB n=500
50 Correct 16 ms 24064 KB n=500
51 Correct 15 ms 24064 KB n=500
52 Correct 16 ms 24064 KB n=500
53 Correct 16 ms 24044 KB n=500
54 Correct 14 ms 24040 KB n=500
55 Correct 14 ms 24064 KB n=278
56 Correct 19 ms 24064 KB n=500
57 Correct 15 ms 24064 KB n=500
58 Correct 14 ms 24064 KB n=500
59 Correct 18 ms 24448 KB n=2000
60 Correct 18 ms 24576 KB n=2000
61 Correct 21 ms 24448 KB n=2000
62 Correct 22 ms 24448 KB n=2000
63 Correct 18 ms 24448 KB n=2000
64 Correct 18 ms 24448 KB n=2000
65 Correct 19 ms 24448 KB n=2000
66 Correct 18 ms 24448 KB n=2000
67 Correct 18 ms 24448 KB n=2000
68 Correct 19 ms 24448 KB n=2000
69 Correct 18 ms 24448 KB n=2000
70 Correct 16 ms 24448 KB n=2000
71 Correct 16 ms 24448 KB n=2000
72 Correct 16 ms 24448 KB n=2000
73 Correct 16 ms 24448 KB n=2000
74 Correct 17 ms 24448 KB n=1844
75 Correct 22 ms 24448 KB n=2000
76 Correct 19 ms 24576 KB n=2000
77 Correct 19 ms 24448 KB n=2000
78 Correct 23 ms 24448 KB n=2000
79 Correct 19 ms 24440 KB n=2000
80 Correct 19 ms 24576 KB n=2000
81 Correct 19 ms 24448 KB n=2000
82 Correct 19 ms 24448 KB n=2000
83 Correct 19 ms 24448 KB n=2000
84 Correct 18 ms 24448 KB n=2000
85 Correct 19 ms 24448 KB n=2000
86 Correct 19 ms 24448 KB n=2000
87 Correct 20 ms 24448 KB n=2000
88 Correct 18 ms 24568 KB n=2000
89 Correct 19 ms 24576 KB n=2000
90 Correct 18 ms 24576 KB n=2000
91 Correct 17 ms 24448 KB n=2000

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23936 KB n=5
2 Correct 17 ms 23936 KB n=100
3 Correct 14 ms 23936 KB n=100
4 Correct 16 ms 23968 KB n=100
5 Correct 15 ms 23936 KB n=100
6 Correct 14 ms 23936 KB n=100
7 Correct 17 ms 23936 KB n=100
8 Correct 17 ms 23936 KB n=100
9 Correct 16 ms 23936 KB n=100
10 Correct 14 ms 23936 KB n=100
11 Correct 19 ms 23936 KB n=100
12 Correct 15 ms 23936 KB n=100
13 Correct 14 ms 23936 KB n=100
14 Correct 14 ms 23936 KB n=100
15 Correct 17 ms 23936 KB n=100
16 Correct 16 ms 23936 KB n=100
17 Correct 19 ms 23936 KB n=100
18 Correct 15 ms 23936 KB n=100
19 Correct 15 ms 23936 KB n=100
20 Correct 14 ms 23936 KB n=100
21 Correct 19 ms 23936 KB n=100
22 Correct 17 ms 23936 KB n=100
23 Correct 14 ms 23936 KB n=100
24 Correct 16 ms 23912 KB n=100
25 Correct 20 ms 23936 KB n=100
26 Correct 14 ms 23936 KB n=12
27 Correct 14 ms 23936 KB n=100
28 Correct 14 ms 24064 KB n=500
29 Correct 15 ms 24040 KB n=500
30 Correct 21 ms 24064 KB n=500
31 Correct 15 ms 24064 KB n=500
32 Correct 15 ms 24056 KB n=500
33 Correct 14 ms 24064 KB n=500
34 Correct 14 ms 24064 KB n=500
35 Correct 15 ms 24064 KB n=500
36 Correct 14 ms 24064 KB n=500
37 Correct 15 ms 24064 KB n=500
38 Correct 14 ms 24064 KB n=500
39 Correct 17 ms 24064 KB n=500
40 Correct 14 ms 24064 KB n=500
41 Correct 18 ms 24064 KB n=500
42 Correct 16 ms 24064 KB n=500
43 Correct 15 ms 24064 KB n=500
44 Correct 15 ms 24064 KB n=500
45 Correct 14 ms 24064 KB n=500
46 Correct 15 ms 24064 KB n=500
47 Correct 18 ms 24064 KB n=500
48 Correct 18 ms 24064 KB n=500
49 Correct 14 ms 24064 KB n=500
50 Correct 16 ms 24064 KB n=500
51 Correct 15 ms 24064 KB n=500
52 Correct 16 ms 24064 KB n=500
53 Correct 16 ms 24044 KB n=500
54 Correct 14 ms 24040 KB n=500
55 Correct 14 ms 24064 KB n=278
56 Correct 19 ms 24064 KB n=500
57 Correct 15 ms 24064 KB n=500
58 Correct 14 ms 24064 KB n=500
59 Correct 18 ms 24448 KB n=2000
60 Correct 18 ms 24576 KB n=2000
61 Correct 21 ms 24448 KB n=2000
62 Correct 22 ms 24448 KB n=2000
63 Correct 18 ms 24448 KB n=2000
64 Correct 18 ms 24448 KB n=2000
65 Correct 19 ms 24448 KB n=2000
66 Correct 18 ms 24448 KB n=2000
67 Correct 18 ms 24448 KB n=2000
68 Correct 19 ms 24448 KB n=2000
69 Correct 18 ms 24448 KB n=2000
70 Correct 16 ms 24448 KB n=2000
71 Correct 16 ms 24448 KB n=2000
72 Correct 16 ms 24448 KB n=2000
73 Correct 16 ms 24448 KB n=2000
74 Correct 17 ms 24448 KB n=1844
75 Correct 22 ms 24448 KB n=2000
76 Correct 19 ms 24576 KB n=2000
77 Correct 19 ms 24448 KB n=2000
78 Correct 23 ms 24448 KB n=2000
79 Correct 19 ms 24440 KB n=2000
80 Correct 19 ms 24576 KB n=2000
81 Correct 19 ms 24448 KB n=2000
82 Correct 19 ms 24448 KB n=2000
83 Correct 19 ms 24448 KB n=2000
84 Correct 18 ms 24448 KB n=2000
85 Correct 19 ms 24448 KB n=2000
86 Correct 19 ms 24448 KB n=2000
87 Correct 20 ms 24448 KB n=2000
88 Correct 18 ms 24568 KB n=2000
89 Correct 19 ms 24576 KB n=2000
90 Correct 18 ms 24576 KB n=2000
91 Correct 17 ms 24448 KB n=2000
92 Correct 1693 ms 74632 KB n=200000
93 Correct 1714 ms 79608 KB n=200000
94 Correct 1679 ms 82940 KB n=200000
95 Correct 1643 ms 74476 KB n=200000
96 Correct 1476 ms 74600 KB n=200000
97 Correct 1872 ms 78584 KB n=200000
98 Correct 1536 ms 74732 KB n=200000
99 Correct 1654 ms 74616 KB n=200000
100 Correct 1479 ms 74520 KB n=200000
101 Correct 1624 ms 84036 KB n=200000
102 Correct 648 ms 75640 KB n=200000
103 Correct 699 ms 75640 KB n=200000
104 Correct 619 ms 75640 KB n=200000
105 Correct 644 ms 76152 KB n=200000
106 Correct 640 ms 76024 KB n=200000
107 Correct 638 ms 76152 KB n=200000
108 Correct 1630 ms 74552 KB n=200000
109 Correct 1504 ms 74488 KB n=200000
110 Correct 1506 ms 74488 KB n=200000
111 Correct 1350 ms 74016 KB n=200000
112 Correct 1655 ms 83056 KB n=200000
113 Correct 1839 ms 78776 KB n=200000
114 Correct 1318 ms 74088 KB n=200000
115 Correct 1868 ms 76792 KB n=200000
116 Correct 1543 ms 74636 KB n=200000
117 Correct 1605 ms 83704 KB n=200000
118 Correct 1745 ms 77560 KB n=200000
119 Correct 1550 ms 74640 KB n=200000
120 Correct 1647 ms 83144 KB n=200000
121 Correct 1536 ms 83192 KB n=200000
122 Correct 1524 ms 83320 KB n=200000
123 Correct 642 ms 75768 KB n=200000
124 Correct 301 ms 38904 KB n=25264