oj.uz

Submission #167557

# Submission time Handle Problem Language Result Execution time Memory
167557 2019-12-09T01:29:18 Z combi1k1 Birthday gift (IZhO18_treearray) C++14
100 / 100
 1212 ms 84216 KB 
#include<bits/stdc++.h>

using namespace std;

const int   N   = 2e5 + 1;

vector<int> g[N];

int p[N][20];
int h[N];

void dfs(int u,int pu)  {
    for(int i = 0 ; i < 17 ; ++i)
        p[u][i + 1] = p[p[u][i]][i];
    for(int v : g[u])   if (v ^ pu) {
        p[v][0] = u;
        h[v] = h[u] + 1;
        dfs(v,u);
    }
}
int par(int u,int d)    {
    for(int i = 0 ; i < 18 ; ++i)   if (d >> i & 1)
        u = p[u][i];
    return  u;
}
int lca(int u,int v)    {
    if (h[u] < h[v])    swap(u,v);

    u = par(u, h[u] - h[v]);

    if (u == v) return  u;

    for(int i = 17 ; i >= 0 ; --i)
        if (p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    return  p[u][0];
}

set<int> pos[N];
set<int> two[N];

int a[N];

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

    int n;  cin >> n;
    int m;  cin >> m;
    int q;  cin >> q;

    for(int i = 1 ; i < n ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1,0);

    for(int i = 1 ; i <= m ; ++i)   {
        cin >> a[i];
        pos[a[i]].insert(i);

        if (i > 1)
            two[lca(a[i - 1],a[i])].insert(i);
    }
    for(int i = 1 ; i <= q ; ++i)   {
        int t;  cin >> t;

        if (t == 1) {
            int p;  cin >> p;
            int v;  cin >> v;

            pos[a[p]].erase(p);

            if (p > 1)  two[lca(a[p],a[p - 1])].erase(p);
            if (p < m)  two[lca(a[p],a[p + 1])].erase(p + 1);

            a[p] = v;

            pos[a[p]].insert(p);

            if (p > 1)  two[lca(a[p],a[p - 1])].insert(p);
            if (p < m)  two[lca(a[p],a[p + 1])].insert(p + 1);
        }
        if (t == 2) {
            int l;  cin >> l;
            int r;  cin >> r;
            int v;  cin >> v;

            if (pos[v].lower_bound(l) != pos[v].upper_bound(r)) {
                int x = (*pos[v].lower_bound(l));

                cout << x << " " << x << "\n";
                continue;
            }
            if (two[v].upper_bound(l) != two[v].upper_bound(r)) {
                int x = (*two[v].upper_bound(l));

                cout << x - 1 << " " << x << "\n";
                continue;
            }
            cout << "-1 -1\n";
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB n=5
2 Correct 23 ms 23800 KB n=100
3 Correct 23 ms 24056 KB n=100
4 Correct 23 ms 23800 KB n=100
5 Correct 23 ms 23800 KB n=100
6 Correct 22 ms 23928 KB n=100
7 Correct 22 ms 23932 KB n=100
8 Correct 22 ms 23800 KB n=100
9 Correct 23 ms 23928 KB n=100
10 Correct 22 ms 23928 KB n=100
11 Correct 23 ms 23800 KB n=100
12 Correct 23 ms 23800 KB n=100
13 Correct 23 ms 23800 KB n=100
14 Correct 23 ms 23800 KB n=100
15 Correct 24 ms 23800 KB n=100
16 Correct 23 ms 23928 KB n=100
17 Correct 24 ms 23800 KB n=100
18 Correct 24 ms 23900 KB n=100
19 Correct 24 ms 23848 KB n=100
20 Correct 23 ms 23936 KB n=100
21 Correct 23 ms 23800 KB n=100
22 Correct 24 ms 23928 KB n=100
23 Correct 23 ms 23800 KB n=100
24 Correct 23 ms 23800 KB n=100
25 Correct 23 ms 23800 KB n=100
26 Correct 24 ms 23800 KB n=12
27 Correct 23 ms 23928 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB n=5
2 Correct 23 ms 23800 KB n=100
3 Correct 23 ms 24056 KB n=100
4 Correct 23 ms 23800 KB n=100
5 Correct 23 ms 23800 KB n=100
6 Correct 22 ms 23928 KB n=100
7 Correct 22 ms 23932 KB n=100
8 Correct 22 ms 23800 KB n=100
9 Correct 23 ms 23928 KB n=100
10 Correct 22 ms 23928 KB n=100
11 Correct 23 ms 23800 KB n=100
12 Correct 23 ms 23800 KB n=100
13 Correct 23 ms 23800 KB n=100
14 Correct 23 ms 23800 KB n=100
15 Correct 24 ms 23800 KB n=100
16 Correct 23 ms 23928 KB n=100
17 Correct 24 ms 23800 KB n=100
18 Correct 24 ms 23900 KB n=100
19 Correct 24 ms 23848 KB n=100
20 Correct 23 ms 23936 KB n=100
21 Correct 23 ms 23800 KB n=100
22 Correct 24 ms 23928 KB n=100
23 Correct 23 ms 23800 KB n=100
24 Correct 23 ms 23800 KB n=100
25 Correct 23 ms 23800 KB n=100
26 Correct 24 ms 23800 KB n=12
27 Correct 23 ms 23928 KB n=100
28 Correct 24 ms 23928 KB n=500
29 Correct 24 ms 23928 KB n=500
30 Correct 24 ms 23976 KB n=500
31 Correct 25 ms 23928 KB n=500
32 Correct 24 ms 23928 KB n=500
33 Correct 24 ms 24056 KB n=500
34 Correct 24 ms 23928 KB n=500
35 Correct 24 ms 23928 KB n=500
36 Correct 24 ms 23928 KB n=500
37 Correct 24 ms 24056 KB n=500
38 Correct 28 ms 24060 KB n=500
39 Correct 24 ms 23928 KB n=500
40 Correct 24 ms 23928 KB n=500
41 Correct 23 ms 23928 KB n=500
42 Correct 25 ms 23928 KB n=500
43 Correct 24 ms 23928 KB n=500
44 Correct 24 ms 23928 KB n=500
45 Correct 24 ms 24028 KB n=500
46 Correct 23 ms 23928 KB n=500
47 Correct 23 ms 23928 KB n=500
48 Correct 24 ms 23928 KB n=500
49 Correct 24 ms 23928 KB n=500
50 Correct 23 ms 23928 KB n=500
51 Correct 24 ms 23928 KB n=500
52 Correct 24 ms 23928 KB n=500
53 Correct 24 ms 23928 KB n=500
54 Correct 24 ms 24056 KB n=500
55 Correct 23 ms 23928 KB n=278
56 Correct 24 ms 23928 KB n=500
57 Correct 24 ms 23928 KB n=500
58 Correct 24 ms 23928 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB n=5
2 Correct 23 ms 23800 KB n=100
3 Correct 23 ms 24056 KB n=100
4 Correct 23 ms 23800 KB n=100
5 Correct 23 ms 23800 KB n=100
6 Correct 22 ms 23928 KB n=100
7 Correct 22 ms 23932 KB n=100
8 Correct 22 ms 23800 KB n=100
9 Correct 23 ms 23928 KB n=100
10 Correct 22 ms 23928 KB n=100
11 Correct 23 ms 23800 KB n=100
12 Correct 23 ms 23800 KB n=100
13 Correct 23 ms 23800 KB n=100
14 Correct 23 ms 23800 KB n=100
15 Correct 24 ms 23800 KB n=100
16 Correct 23 ms 23928 KB n=100
17 Correct 24 ms 23800 KB n=100
18 Correct 24 ms 23900 KB n=100
19 Correct 24 ms 23848 KB n=100
20 Correct 23 ms 23936 KB n=100
21 Correct 23 ms 23800 KB n=100
22 Correct 24 ms 23928 KB n=100
23 Correct 23 ms 23800 KB n=100
24 Correct 23 ms 23800 KB n=100
25 Correct 23 ms 23800 KB n=100
26 Correct 24 ms 23800 KB n=12
27 Correct 23 ms 23928 KB n=100
28 Correct 24 ms 23928 KB n=500
29 Correct 24 ms 23928 KB n=500
30 Correct 24 ms 23976 KB n=500
31 Correct 25 ms 23928 KB n=500
32 Correct 24 ms 23928 KB n=500
33 Correct 24 ms 24056 KB n=500
34 Correct 24 ms 23928 KB n=500
35 Correct 24 ms 23928 KB n=500
36 Correct 24 ms 23928 KB n=500
37 Correct 24 ms 24056 KB n=500
38 Correct 28 ms 24060 KB n=500
39 Correct 24 ms 23928 KB n=500
40 Correct 24 ms 23928 KB n=500
41 Correct 23 ms 23928 KB n=500
42 Correct 25 ms 23928 KB n=500
43 Correct 24 ms 23928 KB n=500
44 Correct 24 ms 23928 KB n=500
45 Correct 24 ms 24028 KB n=500
46 Correct 23 ms 23928 KB n=500
47 Correct 23 ms 23928 KB n=500
48 Correct 24 ms 23928 KB n=500
49 Correct 24 ms 23928 KB n=500
50 Correct 23 ms 23928 KB n=500
51 Correct 24 ms 23928 KB n=500
52 Correct 24 ms 23928 KB n=500
53 Correct 24 ms 23928 KB n=500
54 Correct 24 ms 24056 KB n=500
55 Correct 23 ms 23928 KB n=278
56 Correct 24 ms 23928 KB n=500
57 Correct 24 ms 23928 KB n=500
58 Correct 24 ms 23928 KB n=500
59 Correct 28 ms 24328 KB n=2000
60 Correct 27 ms 24440 KB n=2000
61 Correct 28 ms 24404 KB n=2000
62 Correct 27 ms 24312 KB n=2000
63 Correct 27 ms 24312 KB n=2000
64 Correct 27 ms 24312 KB n=2000
65 Correct 27 ms 24312 KB n=2000
66 Correct 27 ms 24312 KB n=2000
67 Correct 28 ms 24400 KB n=2000
68 Correct 27 ms 24312 KB n=2000
69 Correct 26 ms 24312 KB n=2000
70 Correct 26 ms 24312 KB n=2000
71 Correct 26 ms 24312 KB n=2000
72 Correct 26 ms 24312 KB n=2000
73 Correct 26 ms 24312 KB n=2000
74 Correct 26 ms 24312 KB n=1844
75 Correct 26 ms 24312 KB n=2000
76 Correct 28 ms 24312 KB n=2000
77 Correct 27 ms 24284 KB n=2000
78 Correct 27 ms 24308 KB n=2000
79 Correct 27 ms 24312 KB n=2000
80 Correct 27 ms 24440 KB n=2000
81 Correct 28 ms 24312 KB n=2000
82 Correct 27 ms 24312 KB n=2000
83 Correct 27 ms 24440 KB n=2000
84 Correct 27 ms 24312 KB n=2000
85 Correct 28 ms 24300 KB n=2000
86 Correct 27 ms 24312 KB n=2000
87 Correct 27 ms 24312 KB n=2000
88 Correct 26 ms 24440 KB n=2000
89 Correct 27 ms 24440 KB n=2000
90 Correct 27 ms 24440 KB n=2000
91 Correct 26 ms 24312 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB n=5
2 Correct 23 ms 23800 KB n=100
3 Correct 23 ms 24056 KB n=100
4 Correct 23 ms 23800 KB n=100
5 Correct 23 ms 23800 KB n=100
6 Correct 22 ms 23928 KB n=100
7 Correct 22 ms 23932 KB n=100
8 Correct 22 ms 23800 KB n=100
9 Correct 23 ms 23928 KB n=100
10 Correct 22 ms 23928 KB n=100
11 Correct 23 ms 23800 KB n=100
12 Correct 23 ms 23800 KB n=100
13 Correct 23 ms 23800 KB n=100
14 Correct 23 ms 23800 KB n=100
15 Correct 24 ms 23800 KB n=100
16 Correct 23 ms 23928 KB n=100
17 Correct 24 ms 23800 KB n=100
18 Correct 24 ms 23900 KB n=100
19 Correct 24 ms 23848 KB n=100
20 Correct 23 ms 23936 KB n=100
21 Correct 23 ms 23800 KB n=100
22 Correct 24 ms 23928 KB n=100
23 Correct 23 ms 23800 KB n=100
24 Correct 23 ms 23800 KB n=100
25 Correct 23 ms 23800 KB n=100
26 Correct 24 ms 23800 KB n=12
27 Correct 23 ms 23928 KB n=100
28 Correct 24 ms 23928 KB n=500
29 Correct 24 ms 23928 KB n=500
30 Correct 24 ms 23976 KB n=500
31 Correct 25 ms 23928 KB n=500
32 Correct 24 ms 23928 KB n=500
33 Correct 24 ms 24056 KB n=500
34 Correct 24 ms 23928 KB n=500
35 Correct 24 ms 23928 KB n=500
36 Correct 24 ms 23928 KB n=500
37 Correct 24 ms 24056 KB n=500
38 Correct 28 ms 24060 KB n=500
39 Correct 24 ms 23928 KB n=500
40 Correct 24 ms 23928 KB n=500
41 Correct 23 ms 23928 KB n=500
42 Correct 25 ms 23928 KB n=500
43 Correct 24 ms 23928 KB n=500
44 Correct 24 ms 23928 KB n=500
45 Correct 24 ms 24028 KB n=500
46 Correct 23 ms 23928 KB n=500
47 Correct 23 ms 23928 KB n=500
48 Correct 24 ms 23928 KB n=500
49 Correct 24 ms 23928 KB n=500
50 Correct 23 ms 23928 KB n=500
51 Correct 24 ms 23928 KB n=500
52 Correct 24 ms 23928 KB n=500
53 Correct 24 ms 23928 KB n=500
54 Correct 24 ms 24056 KB n=500
55 Correct 23 ms 23928 KB n=278
56 Correct 24 ms 23928 KB n=500
57 Correct 24 ms 23928 KB n=500
58 Correct 24 ms 23928 KB n=500
59 Correct 28 ms 24328 KB n=2000
60 Correct 27 ms 24440 KB n=2000
61 Correct 28 ms 24404 KB n=2000
62 Correct 27 ms 24312 KB n=2000
63 Correct 27 ms 24312 KB n=2000
64 Correct 27 ms 24312 KB n=2000
65 Correct 27 ms 24312 KB n=2000
66 Correct 27 ms 24312 KB n=2000
67 Correct 28 ms 24400 KB n=2000
68 Correct 27 ms 24312 KB n=2000
69 Correct 26 ms 24312 KB n=2000
70 Correct 26 ms 24312 KB n=2000
71 Correct 26 ms 24312 KB n=2000
72 Correct 26 ms 24312 KB n=2000
73 Correct 26 ms 24312 KB n=2000
74 Correct 26 ms 24312 KB n=1844
75 Correct 26 ms 24312 KB n=2000
76 Correct 28 ms 24312 KB n=2000
77 Correct 27 ms 24284 KB n=2000
78 Correct 27 ms 24308 KB n=2000
79 Correct 27 ms 24312 KB n=2000
80 Correct 27 ms 24440 KB n=2000
81 Correct 28 ms 24312 KB n=2000
82 Correct 27 ms 24312 KB n=2000
83 Correct 27 ms 24440 KB n=2000
84 Correct 27 ms 24312 KB n=2000
85 Correct 28 ms 24300 KB n=2000
86 Correct 27 ms 24312 KB n=2000
87 Correct 27 ms 24312 KB n=2000
88 Correct 26 ms 24440 KB n=2000
89 Correct 27 ms 24440 KB n=2000
90 Correct 27 ms 24440 KB n=2000
91 Correct 26 ms 24312 KB n=2000
92 Correct 931 ms 74628 KB n=200000
93 Correct 1122 ms 79480 KB n=200000
94 Correct 1155 ms 83064 KB n=200000
95 Correct 884 ms 74516 KB n=200000
96 Correct 806 ms 74444 KB n=200000
97 Correct 1177 ms 78632 KB n=200000
98 Correct 835 ms 74604 KB n=200000
99 Correct 1004 ms 74884 KB n=200000
100 Correct 834 ms 74608 KB n=200000
101 Correct 1149 ms 84216 KB n=200000
102 Correct 530 ms 75568 KB n=200000
103 Correct 530 ms 75640 KB n=200000
104 Correct 535 ms 75640 KB n=200000
105 Correct 542 ms 75980 KB n=200000
106 Correct 577 ms 76016 KB n=200000
107 Correct 607 ms 76020 KB n=200000
108 Correct 1008 ms 74600 KB n=200000
109 Correct 951 ms 74616 KB n=200000
110 Correct 965 ms 74700 KB n=200000
111 Correct 876 ms 74004 KB n=200000
112 Correct 1120 ms 83264 KB n=200000
113 Correct 1177 ms 78752 KB n=200000
114 Correct 888 ms 74216 KB n=200000
115 Correct 1212 ms 76452 KB n=200000
116 Correct 819 ms 74704 KB n=200000
117 Correct 1140 ms 83756 KB n=200000
118 Correct 1118 ms 77688 KB n=200000
119 Correct 856 ms 74544 KB n=200000
120 Correct 1157 ms 83136 KB n=200000
121 Correct 1098 ms 83124 KB n=200000
122 Correct 1132 ms 83568 KB n=200000
123 Correct 547 ms 75740 KB n=200000
124 Correct 274 ms 38832 KB n=25264