답안 #90717 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90717	2018-12-24T00:36:04 Z	janchomath	Birthday gift (IZhO18_treearray)	C++14	100 / 100	2215 ms	113384 KB

treearray

#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;

ll in[200020],l,r,n,m,xx,yy,q,a[200020],type,pa;
ll out[200020];
ll timer=1;
ll P[200020][18];
vector<ll>v[200005],g;

void dfs(int p,int u) {
    P[u][0]=p;
    for (int i=1;i<=17;i++)
        P[u][i]=P[P[u][i-1]][i-1];
    timer++;
    in[u]=timer;
    for (int i=0;i<v[u].size();i++)
        if (v[u][i] != p){
            dfs(u,v[u][i]);
        }
    out[u]=timer;
}

int lca(int a,int b) {
    if (in[a] <= in[b] && out[b] <= out[a]) return a;
    for (int i=17;i>=0;i--)
        if (P[a][i])
            if (!(in[P[a][i]] <= in[b] && out[b] <= out[P[a][i]]))
                a=P[a][i];
    return P[a][0];
}

set<ll>st[200005],st1[200005],st2[200005];

int main(){
	
	cin >> n >> m >> q;
	
	for(int i=1; i<n; i++){
		cin >> xx >> yy;
		v[xx].pb(yy);
		v[yy].pb(xx);
	}
	
	dfs(1,1);
	
	for(int i=1; i<=m; i++){
		cin >> a[i];
	}
	
	for(int i=1; i<=m; i++){
		xx = i;
		yy = a[i];
			st[yy].insert(xx);
			if(xx != 1){
				ll pp = lca(a[xx],a[xx-1]);
				pp = lca(yy,a[xx-1]);
				st1[pp].insert(xx-1);
			}
			if(xx != m){
				ll pp = lca(a[xx],a[xx+1]);
				pp = lca(yy,a[xx+1]);
				st2[pp].insert(xx+1);
			}
			a[xx] = yy;
	}
	
	while(q--){
		cin >> type;
		if(type == 1){
			cin >> xx >> yy;
			st[a[xx]].erase(st[a[xx]].find(xx));
			st[yy].insert(xx);
			if(xx != m){
				ll pp = lca(a[xx],a[xx+1]);
				st1[pp].erase(st1[pp].find(xx));
				pp = lca(yy,a[xx+1]);
				st1[pp].insert(xx);
			}
			if(xx != 1){
				ll pp = lca(a[xx],a[xx-1]);
				st1[pp].erase(st1[pp].find(xx-1));
				pp = lca(yy,a[xx-1]);
				st1[pp].insert(xx-1);
			}
			a[xx] = yy;
		}
		else {
			cin >> l >> r >> pa;
			if(st[pa].lower_bound(l) != st[pa].end()){
				if(*(st[pa].lower_bound(l)) <= r){
					cout << *(st[pa].lower_bound(l)) << " " << *(st[pa].lower_bound(l)) << endl;
					continue;
				}
			}
			
			if(st1[pa].lower_bound(l) != st1[pa].end()){
				if(*(st1[pa].lower_bound(l)) < r){
					cout << *(st1[pa].lower_bound(l))<< " " << *(st1[pa].lower_bound(l)) + 1<< endl;
					continue;
				}
			}
			
			cout <<"-1 -1\n";
		}
	}
	
	
	
	
	return 0;
}

Compilation message

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[u].size();i++)
                  ~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	33244 KB	n=5
2	Correct	26 ms	33276 KB	n=100
3	Correct	27 ms	33352 KB	n=100
4	Correct	27 ms	33372 KB	n=100
5	Correct	27 ms	33452 KB	n=100
6	Correct	26 ms	33484 KB	n=100
7	Correct	27 ms	33484 KB	n=100
8	Correct	27 ms	33536 KB	n=100
9	Correct	27 ms	33540 KB	n=100
10	Correct	32 ms	33672 KB	n=100
11	Correct	26 ms	33672 KB	n=100
12	Correct	26 ms	33672 KB	n=100
13	Correct	31 ms	33672 KB	n=100
14	Correct	31 ms	33672 KB	n=100
15	Correct	26 ms	33672 KB	n=100
16	Correct	26 ms	33672 KB	n=100
17	Correct	31 ms	33672 KB	n=100
18	Correct	31 ms	33672 KB	n=100
19	Correct	31 ms	33672 KB	n=100
20	Correct	31 ms	33672 KB	n=100
21	Correct	32 ms	33672 KB	n=100
22	Correct	27 ms	33672 KB	n=100
23	Correct	32 ms	33672 KB	n=100
24	Correct	27 ms	33672 KB	n=100
25	Correct	27 ms	33672 KB	n=100
26	Correct	26 ms	33672 KB	n=12
27	Correct	28 ms	33672 KB	n=100

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	33244 KB	n=5
2	Correct	26 ms	33276 KB	n=100
3	Correct	27 ms	33352 KB	n=100
4	Correct	27 ms	33372 KB	n=100
5	Correct	27 ms	33452 KB	n=100
6	Correct	26 ms	33484 KB	n=100
7	Correct	27 ms	33484 KB	n=100
8	Correct	27 ms	33536 KB	n=100
9	Correct	27 ms	33540 KB	n=100
10	Correct	32 ms	33672 KB	n=100
11	Correct	26 ms	33672 KB	n=100
12	Correct	26 ms	33672 KB	n=100
13	Correct	31 ms	33672 KB	n=100
14	Correct	31 ms	33672 KB	n=100
15	Correct	26 ms	33672 KB	n=100
16	Correct	26 ms	33672 KB	n=100
17	Correct	31 ms	33672 KB	n=100
18	Correct	31 ms	33672 KB	n=100
19	Correct	31 ms	33672 KB	n=100
20	Correct	31 ms	33672 KB	n=100
21	Correct	32 ms	33672 KB	n=100
22	Correct	27 ms	33672 KB	n=100
23	Correct	32 ms	33672 KB	n=100
24	Correct	27 ms	33672 KB	n=100
25	Correct	27 ms	33672 KB	n=100
26	Correct	26 ms	33672 KB	n=12
27	Correct	28 ms	33672 KB	n=100
28	Correct	28 ms	33672 KB	n=500
29	Correct	33 ms	33748 KB	n=500
30	Correct	33 ms	33764 KB	n=500
31	Correct	33 ms	33780 KB	n=500
32	Correct	33 ms	33780 KB	n=500
33	Correct	35 ms	33808 KB	n=500
34	Correct	32 ms	33808 KB	n=500
35	Correct	33 ms	33836 KB	n=500
36	Correct	33 ms	33852 KB	n=500
37	Correct	30 ms	33852 KB	n=500
38	Correct	28 ms	33876 KB	n=500
39	Correct	29 ms	33888 KB	n=500
40	Correct	42 ms	33904 KB	n=500
41	Correct	33 ms	33920 KB	n=500
42	Correct	29 ms	33920 KB	n=500
43	Correct	33 ms	33920 KB	n=500
44	Correct	34 ms	33940 KB	n=500
45	Correct	33 ms	33940 KB	n=500
46	Correct	28 ms	33984 KB	n=500
47	Correct	28 ms	34000 KB	n=500
48	Correct	27 ms	34016 KB	n=500
49	Correct	28 ms	34024 KB	n=500
50	Correct	28 ms	34044 KB	n=500
51	Correct	28 ms	34056 KB	n=500
52	Correct	28 ms	34076 KB	n=500
53	Correct	28 ms	34088 KB	n=500
54	Correct	28 ms	34104 KB	n=500
55	Correct	27 ms	34104 KB	n=278
56	Correct	28 ms	34124 KB	n=500
57	Correct	28 ms	34136 KB	n=500
58	Correct	30 ms	34148 KB	n=500

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	33244 KB	n=5
2	Correct	26 ms	33276 KB	n=100
3	Correct	27 ms	33352 KB	n=100
4	Correct	27 ms	33372 KB	n=100
5	Correct	27 ms	33452 KB	n=100
6	Correct	26 ms	33484 KB	n=100
7	Correct	27 ms	33484 KB	n=100
8	Correct	27 ms	33536 KB	n=100
9	Correct	27 ms	33540 KB	n=100
10	Correct	32 ms	33672 KB	n=100
11	Correct	26 ms	33672 KB	n=100
12	Correct	26 ms	33672 KB	n=100
13	Correct	31 ms	33672 KB	n=100
14	Correct	31 ms	33672 KB	n=100
15	Correct	26 ms	33672 KB	n=100
16	Correct	26 ms	33672 KB	n=100
17	Correct	31 ms	33672 KB	n=100
18	Correct	31 ms	33672 KB	n=100
19	Correct	31 ms	33672 KB	n=100
20	Correct	31 ms	33672 KB	n=100
21	Correct	32 ms	33672 KB	n=100
22	Correct	27 ms	33672 KB	n=100
23	Correct	32 ms	33672 KB	n=100
24	Correct	27 ms	33672 KB	n=100
25	Correct	27 ms	33672 KB	n=100
26	Correct	26 ms	33672 KB	n=12
27	Correct	28 ms	33672 KB	n=100
28	Correct	28 ms	33672 KB	n=500
29	Correct	33 ms	33748 KB	n=500
30	Correct	33 ms	33764 KB	n=500
31	Correct	33 ms	33780 KB	n=500
32	Correct	33 ms	33780 KB	n=500
33	Correct	35 ms	33808 KB	n=500
34	Correct	32 ms	33808 KB	n=500
35	Correct	33 ms	33836 KB	n=500
36	Correct	33 ms	33852 KB	n=500
37	Correct	30 ms	33852 KB	n=500
38	Correct	28 ms	33876 KB	n=500
39	Correct	29 ms	33888 KB	n=500
40	Correct	42 ms	33904 KB	n=500
41	Correct	33 ms	33920 KB	n=500
42	Correct	29 ms	33920 KB	n=500
43	Correct	33 ms	33920 KB	n=500
44	Correct	34 ms	33940 KB	n=500
45	Correct	33 ms	33940 KB	n=500
46	Correct	28 ms	33984 KB	n=500
47	Correct	28 ms	34000 KB	n=500
48	Correct	27 ms	34016 KB	n=500
49	Correct	28 ms	34024 KB	n=500
50	Correct	28 ms	34044 KB	n=500
51	Correct	28 ms	34056 KB	n=500
52	Correct	28 ms	34076 KB	n=500
53	Correct	28 ms	34088 KB	n=500
54	Correct	28 ms	34104 KB	n=500
55	Correct	27 ms	34104 KB	n=278
56	Correct	28 ms	34124 KB	n=500
57	Correct	28 ms	34136 KB	n=500
58	Correct	30 ms	34148 KB	n=500
59	Correct	33 ms	34548 KB	n=2000
60	Correct	34 ms	34728 KB	n=2000
61	Correct	38 ms	34728 KB	n=2000
62	Correct	39 ms	34728 KB	n=2000
63	Correct	40 ms	34728 KB	n=2000
64	Correct	40 ms	34828 KB	n=2000
65	Correct	39 ms	34900 KB	n=2000
66	Correct	40 ms	34968 KB	n=2000
67	Correct	40 ms	35040 KB	n=2000
68	Correct	39 ms	35096 KB	n=2000
69	Correct	35 ms	35172 KB	n=2000
70	Correct	35 ms	35204 KB	n=2000
71	Correct	35 ms	35260 KB	n=2000
72	Correct	35 ms	35308 KB	n=2000
73	Correct	35 ms	35364 KB	n=2000
74	Correct	34 ms	35420 KB	n=1844
75	Correct	34 ms	35464 KB	n=2000
76	Correct	41 ms	35564 KB	n=2000
77	Correct	40 ms	35612 KB	n=2000
78	Correct	39 ms	35624 KB	n=2000
79	Correct	39 ms	35680 KB	n=2000
80	Correct	39 ms	35808 KB	n=2000
81	Correct	40 ms	35808 KB	n=2000
82	Correct	40 ms	35808 KB	n=2000
83	Correct	41 ms	35884 KB	n=2000
84	Correct	40 ms	35940 KB	n=2000
85	Correct	40 ms	36068 KB	n=2000
86	Correct	40 ms	36068 KB	n=2000
87	Correct	39 ms	36108 KB	n=2000
88	Correct	38 ms	36284 KB	n=2000
89	Correct	34 ms	36332 KB	n=2000
90	Correct	34 ms	36388 KB	n=2000
91	Correct	35 ms	36388 KB	n=2000

Subtask #4
44.0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	33244 KB	n=5
2	Correct	26 ms	33276 KB	n=100
3	Correct	27 ms	33352 KB	n=100
4	Correct	27 ms	33372 KB	n=100
5	Correct	27 ms	33452 KB	n=100
6	Correct	26 ms	33484 KB	n=100
7	Correct	27 ms	33484 KB	n=100
8	Correct	27 ms	33536 KB	n=100
9	Correct	27 ms	33540 KB	n=100
10	Correct	32 ms	33672 KB	n=100
11	Correct	26 ms	33672 KB	n=100
12	Correct	26 ms	33672 KB	n=100
13	Correct	31 ms	33672 KB	n=100
14	Correct	31 ms	33672 KB	n=100
15	Correct	26 ms	33672 KB	n=100
16	Correct	26 ms	33672 KB	n=100
17	Correct	31 ms	33672 KB	n=100
18	Correct	31 ms	33672 KB	n=100
19	Correct	31 ms	33672 KB	n=100
20	Correct	31 ms	33672 KB	n=100
21	Correct	32 ms	33672 KB	n=100
22	Correct	27 ms	33672 KB	n=100
23	Correct	32 ms	33672 KB	n=100
24	Correct	27 ms	33672 KB	n=100
25	Correct	27 ms	33672 KB	n=100
26	Correct	26 ms	33672 KB	n=12
27	Correct	28 ms	33672 KB	n=100
28	Correct	28 ms	33672 KB	n=500
29	Correct	33 ms	33748 KB	n=500
30	Correct	33 ms	33764 KB	n=500
31	Correct	33 ms	33780 KB	n=500
32	Correct	33 ms	33780 KB	n=500
33	Correct	35 ms	33808 KB	n=500
34	Correct	32 ms	33808 KB	n=500
35	Correct	33 ms	33836 KB	n=500
36	Correct	33 ms	33852 KB	n=500
37	Correct	30 ms	33852 KB	n=500
38	Correct	28 ms	33876 KB	n=500
39	Correct	29 ms	33888 KB	n=500
40	Correct	42 ms	33904 KB	n=500
41	Correct	33 ms	33920 KB	n=500
42	Correct	29 ms	33920 KB	n=500
43	Correct	33 ms	33920 KB	n=500
44	Correct	34 ms	33940 KB	n=500
45	Correct	33 ms	33940 KB	n=500
46	Correct	28 ms	33984 KB	n=500
47	Correct	28 ms	34000 KB	n=500
48	Correct	27 ms	34016 KB	n=500
49	Correct	28 ms	34024 KB	n=500
50	Correct	28 ms	34044 KB	n=500
51	Correct	28 ms	34056 KB	n=500
52	Correct	28 ms	34076 KB	n=500
53	Correct	28 ms	34088 KB	n=500
54	Correct	28 ms	34104 KB	n=500
55	Correct	27 ms	34104 KB	n=278
56	Correct	28 ms	34124 KB	n=500
57	Correct	28 ms	34136 KB	n=500
58	Correct	30 ms	34148 KB	n=500
59	Correct	33 ms	34548 KB	n=2000
60	Correct	34 ms	34728 KB	n=2000
61	Correct	38 ms	34728 KB	n=2000
62	Correct	39 ms	34728 KB	n=2000
63	Correct	40 ms	34728 KB	n=2000
64	Correct	40 ms	34828 KB	n=2000
65	Correct	39 ms	34900 KB	n=2000
66	Correct	40 ms	34968 KB	n=2000
67	Correct	40 ms	35040 KB	n=2000
68	Correct	39 ms	35096 KB	n=2000
69	Correct	35 ms	35172 KB	n=2000
70	Correct	35 ms	35204 KB	n=2000
71	Correct	35 ms	35260 KB	n=2000
72	Correct	35 ms	35308 KB	n=2000
73	Correct	35 ms	35364 KB	n=2000
74	Correct	34 ms	35420 KB	n=1844
75	Correct	34 ms	35464 KB	n=2000
76	Correct	41 ms	35564 KB	n=2000
77	Correct	40 ms	35612 KB	n=2000
78	Correct	39 ms	35624 KB	n=2000
79	Correct	39 ms	35680 KB	n=2000
80	Correct	39 ms	35808 KB	n=2000
81	Correct	40 ms	35808 KB	n=2000
82	Correct	40 ms	35808 KB	n=2000
83	Correct	41 ms	35884 KB	n=2000
84	Correct	40 ms	35940 KB	n=2000
85	Correct	40 ms	36068 KB	n=2000
86	Correct	40 ms	36068 KB	n=2000
87	Correct	39 ms	36108 KB	n=2000
88	Correct	38 ms	36284 KB	n=2000
89	Correct	34 ms	36332 KB	n=2000
90	Correct	34 ms	36388 KB	n=2000
91	Correct	35 ms	36388 KB	n=2000
92	Correct	1590 ms	90520 KB	n=200000
93	Correct	2170 ms	96732 KB	n=200000
94	Correct	2092 ms	100472 KB	n=200000
95	Correct	1584 ms	100472 KB	n=200000
96	Correct	1539 ms	100472 KB	n=200000
97	Correct	2215 ms	100472 KB	n=200000
98	Correct	1515 ms	100472 KB	n=200000
99	Correct	1733 ms	100472 KB	n=200000
100	Correct	1543 ms	100472 KB	n=200000
101	Correct	1972 ms	108296 KB	n=200000
102	Correct	1152 ms	108296 KB	n=200000
103	Correct	1089 ms	108296 KB	n=200000
104	Correct	1113 ms	108296 KB	n=200000
105	Correct	1215 ms	108296 KB	n=200000
106	Correct	1208 ms	108296 KB	n=200000
107	Correct	1229 ms	108296 KB	n=200000
108	Correct	1520 ms	108296 KB	n=200000
109	Correct	1428 ms	108296 KB	n=200000
110	Correct	1410 ms	108296 KB	n=200000
111	Correct	1539 ms	108296 KB	n=200000
112	Correct	1964 ms	110124 KB	n=200000
113	Correct	1825 ms	110124 KB	n=200000
114	Correct	1329 ms	110124 KB	n=200000
115	Correct	2001 ms	110124 KB	n=200000
116	Correct	1544 ms	110124 KB	n=200000
117	Correct	1869 ms	110388 KB	n=200000
118	Correct	2191 ms	110388 KB	n=200000
119	Correct	1445 ms	110388 KB	n=200000
120	Correct	1968 ms	113044 KB	n=200000
121	Correct	1944 ms	113044 KB	n=200000
122	Correct	1997 ms	113384 KB	n=200000
123	Correct	1250 ms	113384 KB	n=200000
124	Correct	539 ms	113384 KB	n=25264

답안 #90717

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