답안 #89721 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89721	2018-12-18T08:14:58 Z	Abelyan	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1678 ms	107212 KB

treearray

#include <bits/stdc++.h>
using namespace std;

const int N=200005;
const int LG=log2(N)+3;

vector<int> g[N];
int anc[N][LG];
int n,m,q,l;
int in[N],out[N],timer;

void dfs(int v,int par=0){
    in[v]=timer++;
    anc[v][0]=par;
    for (int i=1;i<=l;i++){
        anc[v][i]=anc[anc[v][i-1]][i-1];
    }
    for (auto to:g[v]){
        if (to==par)continue;
        dfs(to,v);
    }
    out[v]=timer++;
}

bool is_anc(int a,int b){
    if (b==0 || a==b)return true;
    if (in[a]>in[b] && in[a]<out[b])return true;
    return false;
}

int lca(int a,int b){
    if (is_anc(a,b)) return b;
    if (is_anc(b,a)) return a;
    for (int i=l;i>=0;i--)
        if (!is_anc(b,anc[a][i]))
            a=anc[a][i];
    return anc[a][0];
}

int a[N];
set<int> sl[N],pr[N];
set<int>::iterator it;
int main(){
    ios_base::sync_with_stdio(false);
    //freopen("input.txt","r",stdin);
    cin>>n>>m>>q;
    l=0;
    while ((1<<l)<=n)l++;
    for (int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1);
    for (int i=1;i<=m;i++){
        cin>>a[i];
        sl[a[i]].insert(i);
        if (i!=1){
            //cout<<lca(a[i],a[i-1])<<" "<<i-1<<endl;
            pr[lca(a[i],a[i-1])].insert(i-1);
            //cout<<lca(a[i],a[i-1])<<" "<<i-1<<endl;
        }
    }
    for (int i=0;i<q;i++){
        int type;
        cin>>type;
        if (type==1){
            int ind,val;
            cin>>ind>>val;
            sl[a[ind]].erase(sl[a[ind]].find(ind));
            sl[val].insert(ind);
            if (ind!=1){
                int oldval=lca(a[ind],a[ind-1]),newval=lca(val,a[ind-1]);
                pr[oldval].erase(pr[oldval].find(ind-1));
                pr[newval].insert(ind-1);
            }
            if (ind!=m){
                int oldval=lca(a[ind],a[ind+1]),newval=lca(val,a[ind+1]);
                //cout<<oldval<<" "<<ind<<endl;
                pr[oldval].erase(pr[oldval].find(ind));
                pr[newval].insert(ind);
            }
            a[ind]=val;
        }
        else{
            int l,r,v;
            cin>>l>>r>>v;
            if (sl[v].size()){
                it=sl[v].lower_bound(l);
                if (it!=sl[v].end() && *it<=r){
                    cout<<*it<<" "<<*it<<endl;
                    continue;
                }
            }
            if (pr[v].size()){
                it=pr[v].lower_bound(l);
                if (it!=pr[v].end() && *it<r){
                    //cout<<*it<<endl;
                    cout<<*it<<" "<<*it+1<<endl;
                    continue;
                }
            }
            cout<<-1<<" "<<-1<<endl;
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	23800 KB	n=5
2	Correct	22 ms	23932 KB	n=100
3	Correct	25 ms	24136 KB	n=100
4	Correct	22 ms	24136 KB	n=100
5	Correct	21 ms	24136 KB	n=100
6	Correct	61 ms	24136 KB	n=100
7	Correct	22 ms	24136 KB	n=100
8	Correct	23 ms	24136 KB	n=100
9	Correct	23 ms	24136 KB	n=100
10	Correct	22 ms	24136 KB	n=100
11	Correct	22 ms	24136 KB	n=100
12	Correct	22 ms	24136 KB	n=100
13	Correct	24 ms	24136 KB	n=100
14	Correct	22 ms	24136 KB	n=100
15	Correct	22 ms	24136 KB	n=100
16	Correct	22 ms	24136 KB	n=100
17	Correct	22 ms	24136 KB	n=100
18	Correct	22 ms	24172 KB	n=100
19	Correct	24 ms	24172 KB	n=100
20	Correct	26 ms	24172 KB	n=100
21	Correct	26 ms	24216 KB	n=100
22	Correct	25 ms	24216 KB	n=100
23	Correct	26 ms	24216 KB	n=100
24	Correct	25 ms	24216 KB	n=100
25	Correct	25 ms	24260 KB	n=100
26	Correct	26 ms	24260 KB	n=12
27	Correct	26 ms	24260 KB	n=100
28	Correct	26 ms	24272 KB	n=500
29	Correct	27 ms	24284 KB	n=500
30	Correct	26 ms	24300 KB	n=500
31	Correct	27 ms	24320 KB	n=500
32	Correct	23 ms	24332 KB	n=500
33	Correct	26 ms	24472 KB	n=500
34	Correct	24 ms	24472 KB	n=500
35	Correct	26 ms	24472 KB	n=500
36	Correct	23 ms	24472 KB	n=500
37	Correct	26 ms	24472 KB	n=500
38	Correct	22 ms	24472 KB	n=500
39	Correct	23 ms	24472 KB	n=500
40	Correct	23 ms	24472 KB	n=500
41	Correct	22 ms	24472 KB	n=500
42	Correct	22 ms	24472 KB	n=500
43	Correct	23 ms	24472 KB	n=500
44	Correct	23 ms	24472 KB	n=500
45	Correct	23 ms	24472 KB	n=500
46	Correct	26 ms	24472 KB	n=500
47	Correct	23 ms	24472 KB	n=500
48	Correct	23 ms	24472 KB	n=500
49	Correct	23 ms	24472 KB	n=500
50	Correct	22 ms	24472 KB	n=500
51	Correct	22 ms	24472 KB	n=500
52	Correct	23 ms	24472 KB	n=500
53	Correct	23 ms	24472 KB	n=500
54	Correct	26 ms	24524 KB	n=500
55	Correct	25 ms	24524 KB	n=278
56	Correct	26 ms	24524 KB	n=500
57	Correct	26 ms	24572 KB	n=500
58	Correct	23 ms	24572 KB	n=500

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	23800 KB	n=5
2	Correct	22 ms	23932 KB	n=100
3	Correct	25 ms	24136 KB	n=100
4	Correct	22 ms	24136 KB	n=100
5	Correct	21 ms	24136 KB	n=100
6	Correct	61 ms	24136 KB	n=100
7	Correct	22 ms	24136 KB	n=100
8	Correct	23 ms	24136 KB	n=100
9	Correct	23 ms	24136 KB	n=100
10	Correct	22 ms	24136 KB	n=100
11	Correct	22 ms	24136 KB	n=100
12	Correct	22 ms	24136 KB	n=100
13	Correct	24 ms	24136 KB	n=100
14	Correct	22 ms	24136 KB	n=100
15	Correct	22 ms	24136 KB	n=100
16	Correct	22 ms	24136 KB	n=100
17	Correct	22 ms	24136 KB	n=100
18	Correct	22 ms	24172 KB	n=100
19	Correct	24 ms	24172 KB	n=100
20	Correct	26 ms	24172 KB	n=100
21	Correct	26 ms	24216 KB	n=100
22	Correct	25 ms	24216 KB	n=100
23	Correct	26 ms	24216 KB	n=100
24	Correct	25 ms	24216 KB	n=100
25	Correct	25 ms	24260 KB	n=100
26	Correct	26 ms	24260 KB	n=12
27	Correct	26 ms	24260 KB	n=100
28	Correct	26 ms	24272 KB	n=500
29	Correct	27 ms	24284 KB	n=500
30	Correct	26 ms	24300 KB	n=500
31	Correct	27 ms	24320 KB	n=500
32	Correct	23 ms	24332 KB	n=500
33	Correct	26 ms	24472 KB	n=500
34	Correct	24 ms	24472 KB	n=500
35	Correct	26 ms	24472 KB	n=500
36	Correct	23 ms	24472 KB	n=500
37	Correct	26 ms	24472 KB	n=500
38	Correct	22 ms	24472 KB	n=500
39	Correct	23 ms	24472 KB	n=500
40	Correct	23 ms	24472 KB	n=500
41	Correct	22 ms	24472 KB	n=500
42	Correct	22 ms	24472 KB	n=500
43	Correct	23 ms	24472 KB	n=500
44	Correct	23 ms	24472 KB	n=500
45	Correct	23 ms	24472 KB	n=500
46	Correct	26 ms	24472 KB	n=500
47	Correct	23 ms	24472 KB	n=500
48	Correct	23 ms	24472 KB	n=500
49	Correct	23 ms	24472 KB	n=500
50	Correct	22 ms	24472 KB	n=500
51	Correct	22 ms	24472 KB	n=500
52	Correct	23 ms	24472 KB	n=500
53	Correct	23 ms	24472 KB	n=500
54	Correct	26 ms	24524 KB	n=500
55	Correct	25 ms	24524 KB	n=278
56	Correct	26 ms	24524 KB	n=500
57	Correct	26 ms	24572 KB	n=500
58	Correct	23 ms	24572 KB	n=500
59	Correct	27 ms	24780 KB	n=2000
60	Correct	27 ms	24908 KB	n=2000
61	Correct	31 ms	24908 KB	n=2000
62	Correct	32 ms	24908 KB	n=2000
63	Correct	28 ms	24908 KB	n=2000
64	Correct	31 ms	24908 KB	n=2000
65	Correct	30 ms	24908 KB	n=2000
66	Correct	30 ms	24908 KB	n=2000
67	Correct	27 ms	24908 KB	n=2000
68	Correct	31 ms	24908 KB	n=2000
69	Correct	31 ms	24908 KB	n=2000
70	Correct	30 ms	24908 KB	n=2000
71	Correct	30 ms	24908 KB	n=2000
72	Correct	31 ms	24908 KB	n=2000
73	Correct	31 ms	24908 KB	n=2000
74	Correct	27 ms	24908 KB	n=1844
75	Correct	32 ms	24964 KB	n=2000
76	Correct	27 ms	24964 KB	n=2000
77	Correct	29 ms	24964 KB	n=2000
78	Correct	30 ms	24964 KB	n=2000
79	Correct	28 ms	24964 KB	n=2000
80	Correct	31 ms	24964 KB	n=2000
81	Correct	30 ms	24964 KB	n=2000
82	Correct	31 ms	24964 KB	n=2000
83	Correct	30 ms	24964 KB	n=2000
84	Correct	30 ms	24964 KB	n=2000
85	Correct	31 ms	24964 KB	n=2000
86	Correct	31 ms	24964 KB	n=2000
87	Correct	30 ms	24964 KB	n=2000
88	Correct	30 ms	24964 KB	n=2000
89	Correct	30 ms	24964 KB	n=2000
90	Correct	30 ms	24964 KB	n=2000
91	Correct	32 ms	24964 KB	n=2000
92	Correct	1238 ms	69776 KB	n=200000
93	Correct	1445 ms	74996 KB	n=200000
94	Correct	1129 ms	78292 KB	n=200000
95	Correct	1271 ms	78292 KB	n=200000
96	Correct	997 ms	78292 KB	n=200000
97	Correct	1268 ms	78292 KB	n=200000
98	Correct	1002 ms	78292 KB	n=200000
99	Correct	1218 ms	78292 KB	n=200000
100	Correct	1211 ms	78292 KB	n=200000
101	Correct	876 ms	91200 KB	n=200000
102	Correct	837 ms	91200 KB	n=200000
103	Correct	939 ms	96992 KB	n=200000
104	Correct	946 ms	99560 KB	n=200000
105	Correct	956 ms	99560 KB	n=200000
106	Correct	930 ms	99560 KB	n=200000
107	Correct	859 ms	99560 KB	n=200000
108	Correct	1090 ms	99560 KB	n=200000
109	Correct	1057 ms	99560 KB	n=200000
110	Correct	1046 ms	99560 KB	n=200000
111	Correct	1120 ms	99560 KB	n=200000
112	Correct	1002 ms	106104 KB	n=200000
113	Correct	1209 ms	106104 KB	n=200000
114	Correct	1155 ms	106104 KB	n=200000
115	Correct	1605 ms	106104 KB	n=200000
116	Correct	1105 ms	106104 KB	n=200000
117	Correct	1126 ms	106424 KB	n=200000
118	Correct	1678 ms	106424 KB	n=200000
119	Correct	1040 ms	106424 KB	n=200000
120	Correct	960 ms	106764 KB	n=200000
121	Correct	957 ms	106956 KB	n=200000
122	Correct	951 ms	107212 KB	n=200000
123	Correct	946 ms	107212 KB	n=200000
124	Correct	274 ms	107212 KB	n=25264

답안 #89721

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 18.0 / 18.0

Subtask #3 26.0 / 26.0

Subtask #4 44.0 / 44.0

Subtask #1
12.0 / 12.0

Subtask #2
18.0 / 18.0

Subtask #3
26.0 / 26.0

Subtask #4
44.0 / 44.0