oj.uz

답안 #456473

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
456473 2021-08-06T21:22:22 Z nafis_shifat Birthday gift (IZhO18_treearray) C++14
100 / 100
 1267 ms 86364 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
using namespace std;
const int mxn=2e5+5;
const int inf=1e9;
vector<int> adj[mxn];
int n,m,q;
int a[mxn];
int dp[20][mxn];
int level[mxn];
int T = 0;
int in[mxn];
int out[mxn];

int inv[mxn];
void dfs(int cur,int prev) {
    in[cur] = ++T;
    inv[T] = cur;
    dp[0][cur] = prev;
    level[cur] = level[prev] + 1;
    for(int i = 1; i < 20; i++) dp[i][cur] = dp[i - 1][dp[i - 1][cur]];
    for(int u : adj[cur]) {
        if(u != prev) dfs(u,cur);
    }
    out[cur] = T;
}



int getLCA(int u,int v) {
    if(level[u] < level[v]) swap(u,v);

    int dif = level[u] - level[v];
    for(int i = 0; i < 20; i++) if((dif >> i) & 1) u = dp[i][u];
    if(u == v) return v;
    for(int i = 19; i >= 0; i--) {
        if(dp[i][u] != dp[i][v]) {
            u = dp[i][u];
            v = dp[i][v];
        }
    }

    return dp[0][u];
}



set<int> pos1[mxn];
set<int> pos2[mxn];


int main() {

    cin >> n >> m >> q;

    for(int i = 1; i < n; i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= m; i++) {
        scanf("%d",&a[i]);
        pos1[a[i]].insert(i);
    }

    
    
    

    dfs(1,0);

    for(int i = 1; i < m; i++) {
        pos2[getLCA(a[i],a[i + 1])].insert(i);
    }


  
    while(q--) {
        int tp;
        scanf("%d",&tp);

        if(tp == 1) {
            int p,v;
            scanf("%d%d",&p,&v);
            pos1[a[p]].erase(p);
            pos1[v].insert(p);

            if(p > 1) {
                int lca = getLCA(a[p - 1],a[p]);
                pos2[lca].erase(p - 1);
                pos2[getLCA(a[p - 1],v)].insert(p - 1);
            }

            if(p < m) {
                int lca = getLCA(a[p],a[p + 1]);
                pos2[lca].erase(p);
                pos2[getLCA(v,a[p + 1])].insert(p);
            }

            
            a[p] = v;


        }  else {
            int l,r,v;
            scanf("%d%d%d",&l,&r,&v);

            auto x = pos1[v].lower_bound(l);

            if(x != pos1[v].end() && *x <= r) {
                int k = *x;
                printf("%d %d\n",k,k);
                continue;
            }

            x = pos2[v].lower_bound(l);

            if(x != pos2[v].end() && *x < r) {
                int k = *x;
                printf("%d %d\n",k,k + 1);
            } else {
                printf("-1 -1\n");
            }
        }
    }










}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
treearray.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d",&tp);
      |         ~~~~~^~~~~~~~~~
treearray.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |             scanf("%d%d",&p,&v);
      |             ~~~~~^~~~~~~~~~~~~~
treearray.cpp:112:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |             scanf("%d%d%d",&l,&r,&v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23884 KB n=5
2 Correct 14 ms 23852 KB n=100
3 Correct 13 ms 23848 KB n=100
4 Correct 13 ms 23848 KB n=100
5 Correct 13 ms 23912 KB n=100
6 Correct 13 ms 23916 KB n=100
7 Correct 13 ms 23884 KB n=100
8 Correct 13 ms 23884 KB n=100
9 Correct 13 ms 23912 KB n=100
10 Correct 13 ms 23936 KB n=100
11 Correct 14 ms 23912 KB n=100
12 Correct 13 ms 23920 KB n=100
13 Correct 13 ms 23884 KB n=100
14 Correct 13 ms 23916 KB n=100
15 Correct 13 ms 23884 KB n=100
16 Correct 13 ms 23912 KB n=100
17 Correct 13 ms 23916 KB n=100
18 Correct 13 ms 23884 KB n=100
19 Correct 13 ms 23884 KB n=100
20 Correct 13 ms 23884 KB n=100
21 Correct 13 ms 23936 KB n=100
22 Correct 14 ms 23884 KB n=100
23 Correct 16 ms 23884 KB n=100
24 Correct 13 ms 23920 KB n=100
25 Correct 14 ms 23896 KB n=100
26 Correct 13 ms 23836 KB n=12
27 Correct 14 ms 23916 KB n=100
28 Correct 14 ms 24052 KB n=500
29 Correct 14 ms 24012 KB n=500
30 Correct 14 ms 24012 KB n=500
31 Correct 14 ms 24012 KB n=500
32 Correct 14 ms 24012 KB n=500
33 Correct 14 ms 24048 KB n=500
34 Correct 14 ms 23992 KB n=500
35 Correct 15 ms 24028 KB n=500
36 Correct 16 ms 24012 KB n=500
37 Correct 14 ms 24012 KB n=500
38 Correct 13 ms 24040 KB n=500
39 Correct 14 ms 23980 KB n=500
40 Correct 14 ms 23936 KB n=500
41 Correct 14 ms 24044 KB n=500
42 Correct 15 ms 23944 KB n=500
43 Correct 15 ms 23924 KB n=500
44 Correct 14 ms 23980 KB n=500
45 Correct 14 ms 24052 KB n=500
46 Correct 14 ms 24056 KB n=500
47 Correct 14 ms 24020 KB n=500
48 Correct 14 ms 24012 KB n=500
49 Correct 14 ms 24012 KB n=500
50 Correct 14 ms 24056 KB n=500
51 Correct 14 ms 24044 KB n=500
52 Correct 14 ms 24020 KB n=500
53 Correct 14 ms 24012 KB n=500
54 Correct 15 ms 24020 KB n=500
55 Correct 13 ms 23916 KB n=278
56 Correct 14 ms 24048 KB n=500
57 Correct 14 ms 24012 KB n=500
58 Correct 14 ms 24020 KB n=500
59 Correct 16 ms 24396 KB n=2000
60 Correct 16 ms 24436 KB n=2000
61 Correct 17 ms 24408 KB n=2000
62 Correct 18 ms 24396 KB n=2000
63 Correct 17 ms 24396 KB n=2000
64 Correct 17 ms 24440 KB n=2000
65 Correct 21 ms 24396 KB n=2000
66 Correct 17 ms 24420 KB n=2000
67 Correct 18 ms 24396 KB n=2000
68 Correct 17 ms 24440 KB n=2000
69 Correct 16 ms 24396 KB n=2000
70 Correct 16 ms 24308 KB n=2000
71 Correct 16 ms 24432 KB n=2000
72 Correct 16 ms 24396 KB n=2000
73 Correct 16 ms 24396 KB n=2000
74 Correct 16 ms 24396 KB n=1844
75 Correct 16 ms 24312 KB n=2000
76 Correct 17 ms 24416 KB n=2000
77 Correct 17 ms 24340 KB n=2000
78 Correct 17 ms 24396 KB n=2000
79 Correct 19 ms 24312 KB n=2000
80 Correct 16 ms 24492 KB n=2000
81 Correct 16 ms 24412 KB n=2000
82 Correct 17 ms 24308 KB n=2000
83 Correct 17 ms 24388 KB n=2000
84 Correct 17 ms 24396 KB n=2000
85 Correct 17 ms 24396 KB n=2000
86 Correct 18 ms 24444 KB n=2000
87 Correct 17 ms 24528 KB n=2000
88 Correct 17 ms 24440 KB n=2000
89 Correct 17 ms 24460 KB n=2000
90 Correct 17 ms 24504 KB n=2000
91 Correct 16 ms 24440 KB n=2000

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23884 KB n=5
2 Correct 14 ms 23852 KB n=100
3 Correct 13 ms 23848 KB n=100
4 Correct 13 ms 23848 KB n=100
5 Correct 13 ms 23912 KB n=100
6 Correct 13 ms 23916 KB n=100
7 Correct 13 ms 23884 KB n=100
8 Correct 13 ms 23884 KB n=100
9 Correct 13 ms 23912 KB n=100
10 Correct 13 ms 23936 KB n=100
11 Correct 14 ms 23912 KB n=100
12 Correct 13 ms 23920 KB n=100
13 Correct 13 ms 23884 KB n=100
14 Correct 13 ms 23916 KB n=100
15 Correct 13 ms 23884 KB n=100
16 Correct 13 ms 23912 KB n=100
17 Correct 13 ms 23916 KB n=100
18 Correct 13 ms 23884 KB n=100
19 Correct 13 ms 23884 KB n=100
20 Correct 13 ms 23884 KB n=100
21 Correct 13 ms 23936 KB n=100
22 Correct 14 ms 23884 KB n=100
23 Correct 16 ms 23884 KB n=100
24 Correct 13 ms 23920 KB n=100
25 Correct 14 ms 23896 KB n=100
26 Correct 13 ms 23836 KB n=12
27 Correct 14 ms 23916 KB n=100
28 Correct 14 ms 24052 KB n=500
29 Correct 14 ms 24012 KB n=500
30 Correct 14 ms 24012 KB n=500
31 Correct 14 ms 24012 KB n=500
32 Correct 14 ms 24012 KB n=500
33 Correct 14 ms 24048 KB n=500
34 Correct 14 ms 23992 KB n=500
35 Correct 15 ms 24028 KB n=500
36 Correct 16 ms 24012 KB n=500
37 Correct 14 ms 24012 KB n=500
38 Correct 13 ms 24040 KB n=500
39 Correct 14 ms 23980 KB n=500
40 Correct 14 ms 23936 KB n=500
41 Correct 14 ms 24044 KB n=500
42 Correct 15 ms 23944 KB n=500
43 Correct 15 ms 23924 KB n=500
44 Correct 14 ms 23980 KB n=500
45 Correct 14 ms 24052 KB n=500
46 Correct 14 ms 24056 KB n=500
47 Correct 14 ms 24020 KB n=500
48 Correct 14 ms 24012 KB n=500
49 Correct 14 ms 24012 KB n=500
50 Correct 14 ms 24056 KB n=500
51 Correct 14 ms 24044 KB n=500
52 Correct 14 ms 24020 KB n=500
53 Correct 14 ms 24012 KB n=500
54 Correct 15 ms 24020 KB n=500
55 Correct 13 ms 23916 KB n=278
56 Correct 14 ms 24048 KB n=500
57 Correct 14 ms 24012 KB n=500
58 Correct 14 ms 24020 KB n=500
59 Correct 16 ms 24396 KB n=2000
60 Correct 16 ms 24436 KB n=2000
61 Correct 17 ms 24408 KB n=2000
62 Correct 18 ms 24396 KB n=2000
63 Correct 17 ms 24396 KB n=2000
64 Correct 17 ms 24440 KB n=2000
65 Correct 21 ms 24396 KB n=2000
66 Correct 17 ms 24420 KB n=2000
67 Correct 18 ms 24396 KB n=2000
68 Correct 17 ms 24440 KB n=2000
69 Correct 16 ms 24396 KB n=2000
70 Correct 16 ms 24308 KB n=2000
71 Correct 16 ms 24432 KB n=2000
72 Correct 16 ms 24396 KB n=2000
73 Correct 16 ms 24396 KB n=2000
74 Correct 16 ms 24396 KB n=1844
75 Correct 16 ms 24312 KB n=2000
76 Correct 17 ms 24416 KB n=2000
77 Correct 17 ms 24340 KB n=2000
78 Correct 17 ms 24396 KB n=2000
79 Correct 19 ms 24312 KB n=2000
80 Correct 16 ms 24492 KB n=2000
81 Correct 16 ms 24412 KB n=2000
82 Correct 17 ms 24308 KB n=2000
83 Correct 17 ms 24388 KB n=2000
84 Correct 17 ms 24396 KB n=2000
85 Correct 17 ms 24396 KB n=2000
86 Correct 18 ms 24444 KB n=2000
87 Correct 17 ms 24528 KB n=2000
88 Correct 17 ms 24440 KB n=2000
89 Correct 17 ms 24460 KB n=2000
90 Correct 17 ms 24504 KB n=2000
91 Correct 16 ms 24440 KB n=2000
92 Correct 1002 ms 76968 KB n=200000
93 Correct 1104 ms 81712 KB n=200000
94 Correct 1020 ms 85024 KB n=200000
95 Correct 910 ms 76712 KB n=200000
96 Correct 872 ms 76732 KB n=200000
97 Correct 1112 ms 80896 KB n=200000
98 Correct 886 ms 76672 KB n=200000
99 Correct 1152 ms 76952 KB n=200000
100 Correct 954 ms 76688 KB n=200000
101 Correct 1028 ms 86364 KB n=200000
102 Correct 549 ms 77860 KB n=200000
103 Correct 572 ms 77876 KB n=200000
104 Correct 538 ms 77792 KB n=200000
105 Correct 560 ms 78408 KB n=200000
106 Correct 543 ms 78276 KB n=200000
107 Correct 552 ms 78212 KB n=200000
108 Correct 1055 ms 76760 KB n=200000
109 Correct 1058 ms 76756 KB n=200000
110 Correct 1032 ms 76684 KB n=200000
111 Correct 927 ms 76100 KB n=200000
112 Correct 1032 ms 85284 KB n=200000
113 Correct 1124 ms 80880 KB n=200000
114 Correct 911 ms 76260 KB n=200000
115 Correct 1267 ms 78632 KB n=200000
116 Correct 890 ms 76948 KB n=200000
117 Correct 1089 ms 85664 KB n=200000
118 Correct 1129 ms 79820 KB n=200000
119 Correct 882 ms 77000 KB n=200000
120 Correct 939 ms 85460 KB n=200000
121 Correct 985 ms 85316 KB n=200000
122 Correct 939 ms 85700 KB n=200000
123 Correct 600 ms 78100 KB n=200000
124 Correct 216 ms 39080 KB n=25264