oj.uz

Submission #431323

# Submission time Handle Problem Language Result Execution time Memory
431323 2021-06-17T11:00:12 Z MilosMilutinovic Birthday gift (IZhO18_treearray) C++14
100 / 100
 1370 ms 85564 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
 
const int N=200050;
const int L=20;
 
int par[N][L],lid[N],rid[N],tid,dep[N];
vector<int> E[N];
 
void DFS(int u,int p){
    par[u][0]=p;
    dep[u]=dep[p]+1;
    for(int i=1;i<L;i++)par[u][i]=par[par[u][i-1]][i-1];
    lid[u]=++tid;
    for(int v:E[u])if(v!=p)DFS(v,u);
    rid[u]=tid;
}
 
bool ancestor(int u,int v){
    return lid[u]<=lid[v]&&rid[v]<=rid[u];
}
 
int LCA(int u,int v){
    if(ancestor(u,v))return u;
    if(ancestor(v,u))return v;
    for(int i=L-1;i>=0;i--){
        if(par[u][i]>0&&!ancestor(par[u][i],v))u=par[u][i];
    }
    return par[u][0];
}
 
int n,m,q,a[N];
set<int> nodes[N][2];
void Update(int i){
    if(i<=0)return;
    nodes[a[i]][1].insert(i);
    if(i<m){
        nodes[LCA(a[i],a[i+1])][0].insert(i);
    }
}
 
void Remove(int i){
    if(i<=0)return;
    nodes[a[i]][1].erase(i);
    if(i<m){
        nodes[LCA(a[i],a[i+1])][0].erase(i);
    }
}
 
int main(){
    scanf("%i%i%i",&n,&m,&q);
    for(int i=1;i<n;i++){
        int u,v;scanf("%i%i",&u,&v);
        E[u].pb(v);
        E[v].pb(u);
    }
    for(int i=1;i<=m;i++)scanf("%i",&a[i]);
    DFS(1,0);
    for(int i=1;i<=m;i++)Update(i);
    while(q--){
        int type;scanf("%i",&type);
        if(type==1){
            int pos,v;scanf("%i%i",&pos,&v);
            Remove(pos-1);
            Remove(pos);
            a[pos]=v;
            Update(pos-1);
            Update(pos);
        }else{
            int l,r,v;scanf("%i%i%i",&l,&r,&v);
            auto x=nodes[v][0].lower_bound(l);
            auto y=nodes[v][1].lower_bound(l);
            if(x!=nodes[v][0].end()&&*x<r){
                printf("%i %i\n",*x,*x+1);
                continue;
            }
            if(y!=nodes[v][1].end()&&*y<=r){
                printf("%i %i\n",*y,*y);
                continue;
            }
            printf("-1 -1\n");
        }
    }
    return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%i%i%i",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:54:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         int u,v;scanf("%i%i",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~
treearray.cpp:58:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     for(int i=1;i<=m;i++)scanf("%i",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~
treearray.cpp:62:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         int type;scanf("%i",&type);
      |                  ~~~~~^~~~~~~~~~~~
treearray.cpp:64:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             int pos,v;scanf("%i%i",&pos,&v);
      |                       ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:71:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |             int l,r,v;scanf("%i%i%i",&l,&r,&v);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB n=5
2 Correct 16 ms 23756 KB n=100
3 Correct 18 ms 23800 KB n=100
4 Correct 17 ms 23764 KB n=100
5 Correct 16 ms 23756 KB n=100
6 Correct 15 ms 23788 KB n=100
7 Correct 16 ms 23756 KB n=100
8 Correct 14 ms 23776 KB n=100
9 Correct 14 ms 23756 KB n=100
10 Correct 17 ms 23832 KB n=100
11 Correct 17 ms 23756 KB n=100
12 Correct 17 ms 23804 KB n=100
13 Correct 14 ms 23756 KB n=100
14 Correct 24 ms 23744 KB n=100
15 Correct 25 ms 23756 KB n=100
16 Correct 17 ms 23844 KB n=100
17 Correct 28 ms 23788 KB n=100
18 Correct 15 ms 23756 KB n=100
19 Correct 16 ms 23756 KB n=100
20 Correct 15 ms 23756 KB n=100
21 Correct 15 ms 23756 KB n=100
22 Correct 16 ms 23756 KB n=100
23 Correct 14 ms 23800 KB n=100
24 Correct 17 ms 23756 KB n=100
25 Correct 17 ms 23756 KB n=100
26 Correct 14 ms 23824 KB n=12
27 Correct 15 ms 23756 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB n=5
2 Correct 16 ms 23756 KB n=100
3 Correct 18 ms 23800 KB n=100
4 Correct 17 ms 23764 KB n=100
5 Correct 16 ms 23756 KB n=100
6 Correct 15 ms 23788 KB n=100
7 Correct 16 ms 23756 KB n=100
8 Correct 14 ms 23776 KB n=100
9 Correct 14 ms 23756 KB n=100
10 Correct 17 ms 23832 KB n=100
11 Correct 17 ms 23756 KB n=100
12 Correct 17 ms 23804 KB n=100
13 Correct 14 ms 23756 KB n=100
14 Correct 24 ms 23744 KB n=100
15 Correct 25 ms 23756 KB n=100
16 Correct 17 ms 23844 KB n=100
17 Correct 28 ms 23788 KB n=100
18 Correct 15 ms 23756 KB n=100
19 Correct 16 ms 23756 KB n=100
20 Correct 15 ms 23756 KB n=100
21 Correct 15 ms 23756 KB n=100
22 Correct 16 ms 23756 KB n=100
23 Correct 14 ms 23800 KB n=100
24 Correct 17 ms 23756 KB n=100
25 Correct 17 ms 23756 KB n=100
26 Correct 14 ms 23824 KB n=12
27 Correct 15 ms 23756 KB n=100
28 Correct 16 ms 23936 KB n=500
29 Correct 17 ms 23928 KB n=500
30 Correct 18 ms 23916 KB n=500
31 Correct 17 ms 23876 KB n=500
32 Correct 17 ms 23940 KB n=500
33 Correct 16 ms 23944 KB n=500
34 Correct 20 ms 23940 KB n=500
35 Correct 15 ms 23884 KB n=500
36 Correct 18 ms 23884 KB n=500
37 Correct 19 ms 23920 KB n=500
38 Correct 17 ms 23824 KB n=500
39 Correct 15 ms 23884 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 17 ms 23884 KB n=500
42 Correct 15 ms 23936 KB n=500
43 Correct 15 ms 23936 KB n=500
44 Correct 15 ms 23852 KB n=500
45 Correct 16 ms 23884 KB n=500
46 Correct 15 ms 23948 KB n=500
47 Correct 15 ms 23884 KB n=500
48 Correct 27 ms 23884 KB n=500
49 Correct 23 ms 23884 KB n=500
50 Correct 16 ms 23884 KB n=500
51 Correct 16 ms 23928 KB n=500
52 Correct 15 ms 23884 KB n=500
53 Correct 15 ms 23948 KB n=500
54 Correct 20 ms 23940 KB n=500
55 Correct 19 ms 23884 KB n=278
56 Correct 18 ms 23904 KB n=500
57 Correct 17 ms 23928 KB n=500
58 Correct 15 ms 23884 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB n=5
2 Correct 16 ms 23756 KB n=100
3 Correct 18 ms 23800 KB n=100
4 Correct 17 ms 23764 KB n=100
5 Correct 16 ms 23756 KB n=100
6 Correct 15 ms 23788 KB n=100
7 Correct 16 ms 23756 KB n=100
8 Correct 14 ms 23776 KB n=100
9 Correct 14 ms 23756 KB n=100
10 Correct 17 ms 23832 KB n=100
11 Correct 17 ms 23756 KB n=100
12 Correct 17 ms 23804 KB n=100
13 Correct 14 ms 23756 KB n=100
14 Correct 24 ms 23744 KB n=100
15 Correct 25 ms 23756 KB n=100
16 Correct 17 ms 23844 KB n=100
17 Correct 28 ms 23788 KB n=100
18 Correct 15 ms 23756 KB n=100
19 Correct 16 ms 23756 KB n=100
20 Correct 15 ms 23756 KB n=100
21 Correct 15 ms 23756 KB n=100
22 Correct 16 ms 23756 KB n=100
23 Correct 14 ms 23800 KB n=100
24 Correct 17 ms 23756 KB n=100
25 Correct 17 ms 23756 KB n=100
26 Correct 14 ms 23824 KB n=12
27 Correct 15 ms 23756 KB n=100
28 Correct 16 ms 23936 KB n=500
29 Correct 17 ms 23928 KB n=500
30 Correct 18 ms 23916 KB n=500
31 Correct 17 ms 23876 KB n=500
32 Correct 17 ms 23940 KB n=500
33 Correct 16 ms 23944 KB n=500
34 Correct 20 ms 23940 KB n=500
35 Correct 15 ms 23884 KB n=500
36 Correct 18 ms 23884 KB n=500
37 Correct 19 ms 23920 KB n=500
38 Correct 17 ms 23824 KB n=500
39 Correct 15 ms 23884 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 17 ms 23884 KB n=500
42 Correct 15 ms 23936 KB n=500
43 Correct 15 ms 23936 KB n=500
44 Correct 15 ms 23852 KB n=500
45 Correct 16 ms 23884 KB n=500
46 Correct 15 ms 23948 KB n=500
47 Correct 15 ms 23884 KB n=500
48 Correct 27 ms 23884 KB n=500
49 Correct 23 ms 23884 KB n=500
50 Correct 16 ms 23884 KB n=500
51 Correct 16 ms 23928 KB n=500
52 Correct 15 ms 23884 KB n=500
53 Correct 15 ms 23948 KB n=500
54 Correct 20 ms 23940 KB n=500
55 Correct 19 ms 23884 KB n=278
56 Correct 18 ms 23904 KB n=500
57 Correct 17 ms 23928 KB n=500
58 Correct 15 ms 23884 KB n=500
59 Correct 21 ms 24264 KB n=2000
60 Correct 25 ms 24324 KB n=2000
61 Correct 23 ms 24324 KB n=2000
62 Correct 21 ms 24268 KB n=2000
63 Correct 23 ms 24428 KB n=2000
64 Correct 18 ms 24268 KB n=2000
65 Correct 21 ms 24316 KB n=2000
66 Correct 17 ms 24316 KB n=2000
67 Correct 27 ms 24276 KB n=2000
68 Correct 18 ms 24240 KB n=2000
69 Correct 17 ms 24324 KB n=2000
70 Correct 22 ms 24324 KB n=2000
71 Correct 17 ms 24268 KB n=2000
72 Correct 20 ms 24196 KB n=2000
73 Correct 17 ms 24268 KB n=2000
74 Correct 23 ms 24268 KB n=1844
75 Correct 17 ms 24316 KB n=2000
76 Correct 27 ms 24268 KB n=2000
77 Correct 20 ms 24320 KB n=2000
78 Correct 19 ms 24268 KB n=2000
79 Correct 18 ms 24188 KB n=2000
80 Correct 17 ms 24360 KB n=2000
81 Correct 17 ms 24344 KB n=2000
82 Correct 20 ms 24216 KB n=2000
83 Correct 20 ms 24268 KB n=2000
84 Correct 22 ms 24268 KB n=2000
85 Correct 19 ms 24320 KB n=2000
86 Correct 20 ms 24268 KB n=2000
87 Correct 21 ms 24312 KB n=2000
88 Correct 20 ms 24340 KB n=2000
89 Correct 20 ms 24400 KB n=2000
90 Correct 19 ms 24320 KB n=2000
91 Correct 20 ms 24184 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB n=5
2 Correct 16 ms 23756 KB n=100
3 Correct 18 ms 23800 KB n=100
4 Correct 17 ms 23764 KB n=100
5 Correct 16 ms 23756 KB n=100
6 Correct 15 ms 23788 KB n=100
7 Correct 16 ms 23756 KB n=100
8 Correct 14 ms 23776 KB n=100
9 Correct 14 ms 23756 KB n=100
10 Correct 17 ms 23832 KB n=100
11 Correct 17 ms 23756 KB n=100
12 Correct 17 ms 23804 KB n=100
13 Correct 14 ms 23756 KB n=100
14 Correct 24 ms 23744 KB n=100
15 Correct 25 ms 23756 KB n=100
16 Correct 17 ms 23844 KB n=100
17 Correct 28 ms 23788 KB n=100
18 Correct 15 ms 23756 KB n=100
19 Correct 16 ms 23756 KB n=100
20 Correct 15 ms 23756 KB n=100
21 Correct 15 ms 23756 KB n=100
22 Correct 16 ms 23756 KB n=100
23 Correct 14 ms 23800 KB n=100
24 Correct 17 ms 23756 KB n=100
25 Correct 17 ms 23756 KB n=100
26 Correct 14 ms 23824 KB n=12
27 Correct 15 ms 23756 KB n=100
28 Correct 16 ms 23936 KB n=500
29 Correct 17 ms 23928 KB n=500
30 Correct 18 ms 23916 KB n=500
31 Correct 17 ms 23876 KB n=500
32 Correct 17 ms 23940 KB n=500
33 Correct 16 ms 23944 KB n=500
34 Correct 20 ms 23940 KB n=500
35 Correct 15 ms 23884 KB n=500
36 Correct 18 ms 23884 KB n=500
37 Correct 19 ms 23920 KB n=500
38 Correct 17 ms 23824 KB n=500
39 Correct 15 ms 23884 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 17 ms 23884 KB n=500
42 Correct 15 ms 23936 KB n=500
43 Correct 15 ms 23936 KB n=500
44 Correct 15 ms 23852 KB n=500
45 Correct 16 ms 23884 KB n=500
46 Correct 15 ms 23948 KB n=500
47 Correct 15 ms 23884 KB n=500
48 Correct 27 ms 23884 KB n=500
49 Correct 23 ms 23884 KB n=500
50 Correct 16 ms 23884 KB n=500
51 Correct 16 ms 23928 KB n=500
52 Correct 15 ms 23884 KB n=500
53 Correct 15 ms 23948 KB n=500
54 Correct 20 ms 23940 KB n=500
55 Correct 19 ms 23884 KB n=278
56 Correct 18 ms 23904 KB n=500
57 Correct 17 ms 23928 KB n=500
58 Correct 15 ms 23884 KB n=500
59 Correct 21 ms 24264 KB n=2000
60 Correct 25 ms 24324 KB n=2000
61 Correct 23 ms 24324 KB n=2000
62 Correct 21 ms 24268 KB n=2000
63 Correct 23 ms 24428 KB n=2000
64 Correct 18 ms 24268 KB n=2000
65 Correct 21 ms 24316 KB n=2000
66 Correct 17 ms 24316 KB n=2000
67 Correct 27 ms 24276 KB n=2000
68 Correct 18 ms 24240 KB n=2000
69 Correct 17 ms 24324 KB n=2000
70 Correct 22 ms 24324 KB n=2000
71 Correct 17 ms 24268 KB n=2000
72 Correct 20 ms 24196 KB n=2000
73 Correct 17 ms 24268 KB n=2000
74 Correct 23 ms 24268 KB n=1844
75 Correct 17 ms 24316 KB n=2000
76 Correct 27 ms 24268 KB n=2000
77 Correct 20 ms 24320 KB n=2000
78 Correct 19 ms 24268 KB n=2000
79 Correct 18 ms 24188 KB n=2000
80 Correct 17 ms 24360 KB n=2000
81 Correct 17 ms 24344 KB n=2000
82 Correct 20 ms 24216 KB n=2000
83 Correct 20 ms 24268 KB n=2000
84 Correct 22 ms 24268 KB n=2000
85 Correct 19 ms 24320 KB n=2000
86 Correct 20 ms 24268 KB n=2000
87 Correct 21 ms 24312 KB n=2000
88 Correct 20 ms 24340 KB n=2000
89 Correct 20 ms 24400 KB n=2000
90 Correct 19 ms 24320 KB n=2000
91 Correct 20 ms 24184 KB n=2000
92 Correct 1104 ms 76028 KB n=200000
93 Correct 1157 ms 80964 KB n=200000
94 Correct 853 ms 84288 KB n=200000
95 Correct 1091 ms 75852 KB n=200000
96 Correct 1054 ms 75888 KB n=200000
97 Correct 1321 ms 80108 KB n=200000
98 Correct 1076 ms 75852 KB n=200000
99 Correct 1232 ms 76032 KB n=200000
100 Correct 986 ms 76004 KB n=200000
101 Correct 681 ms 85564 KB n=200000
102 Correct 556 ms 77132 KB n=200000
103 Correct 604 ms 77104 KB n=200000
104 Correct 617 ms 77080 KB n=200000
105 Correct 587 ms 77532 KB n=200000
106 Correct 564 ms 77496 KB n=200000
107 Correct 562 ms 77456 KB n=200000
108 Correct 993 ms 76008 KB n=200000
109 Correct 1014 ms 75908 KB n=200000
110 Correct 1010 ms 76016 KB n=200000
111 Correct 974 ms 75372 KB n=200000
112 Correct 704 ms 84600 KB n=200000
113 Correct 1079 ms 79948 KB n=200000
114 Correct 977 ms 75472 KB n=200000
115 Correct 1370 ms 77944 KB n=200000
116 Correct 872 ms 75976 KB n=200000
117 Correct 674 ms 84956 KB n=200000
118 Correct 1314 ms 78852 KB n=200000
119 Correct 946 ms 76052 KB n=200000
120 Correct 672 ms 84576 KB n=200000
121 Correct 632 ms 84584 KB n=200000
122 Correct 647 ms 84772 KB n=200000
123 Correct 613 ms 77224 KB n=200000
124 Correct 239 ms 38856 KB n=25264