oj.uz

Submission #522716

# Submission time Handle Problem Language Result Execution time Memory
522716 2022-02-05T14:05:41 Z inluminas Birthday gift (IZhO18_treearray) C++17
100 / 100
 1197 ms 86444 KB 
#include"bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=2e5+10;
vector<int>adj[lmt];
int lvl[lmt],par[lmt][20];
set<int>s[lmt],pre[lmt];

void dfs(int u,int p){
  for(int v:adj[u]){
    if(v==p) continue;
    lvl[v]=lvl[u]+1;
    par[v][0]=u;
    dfs(v,u);
  }
}

int lca(int p,int q){
  if(lvl[p]<lvl[q]) swap(p,q);
  for(int i=19;i>=0;i--){
    if(lvl[p]-(1<<i)>=lvl[q]){
      p=par[p][i];
    }
  }
  if(p==q) return p;
  for(int i=19;i>=0;i--){
    if(par[p][i]!=-1 && par[p][i]!=par[q][i]){
      p=par[p][i],q=par[q][i];
    }
  }
  return par[p][0];
}

int main(){
  fastio;

  for(int i=0;i<lmt;i++){
    for(int j=0;j<20;j++) par[i][j]=-1;
  }

  int n,m,k;
  cin>>n>>m>>k;
  for(int i=1;i<n;i++){
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1,0);
  for(int j=1;j<20;j++){
    for(int i=1;i<=n;i++){
      if(par[i][j-1]==-1) continue;
      par[i][j]=par[par[i][j-1]][j-1];
    }
  }

  int a[m+1];
  for(int i=1;i<=m;i++){
    cin>>a[i];
    pre[a[i]].insert(i);
    if(i==1) continue;
    int p=lca(a[i-1],a[i]);
    s[p].insert(i-1);
  }

  while(k--){
    int t;
    cin>>t;
    if(t==1){
      int pos,v;
      cin>>pos>>v;
      pre[a[pos]].erase(pos);
      pre[v].insert(pos);
      if(pos>1) s[lca(a[pos-1],a[pos])].erase(pos-1);
      if(pos<m) s[lca(a[pos],a[pos+1])].erase(pos);
      a[pos]=v;
      if(pos>1) s[lca(a[pos-1],a[pos])].insert(pos-1);
      if(pos<m) s[lca(a[pos],a[pos+1])].insert(pos);
    }else{
      int l,r,v;
      cin>>l>>r>>v;
      auto it=s[v].lower_bound(l);
      if(it!=s[v].end() && (*it)+1<=r) cout<<(*it)<<" "<<(*it)+1<<endl;
      else{
        it=pre[v].lower_bound(l);
        if(it!=pre[v].end() && (*it)<=r) cout<<(*it)<<" "<<(*it)<<endl;
        else cout<<-1<<" "<<-1<<endl;
      }
    }
  }
  return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39372 KB n=5
2 Correct 19 ms 39372 KB n=100
3 Correct 18 ms 39436 KB n=100
4 Correct 17 ms 39372 KB n=100
5 Correct 17 ms 39372 KB n=100
6 Correct 17 ms 39420 KB n=100
7 Correct 18 ms 39372 KB n=100
8 Correct 18 ms 39436 KB n=100
9 Correct 18 ms 39364 KB n=100
10 Correct 17 ms 39372 KB n=100
11 Correct 17 ms 39468 KB n=100
12 Correct 24 ms 39440 KB n=100
13 Correct 18 ms 39388 KB n=100
14 Correct 18 ms 39412 KB n=100
15 Correct 20 ms 39364 KB n=100
16 Correct 19 ms 39440 KB n=100
17 Correct 18 ms 39372 KB n=100
18 Correct 19 ms 39484 KB n=100
19 Correct 18 ms 39372 KB n=100
20 Correct 18 ms 39440 KB n=100
21 Correct 20 ms 39440 KB n=100
22 Correct 18 ms 39408 KB n=100
23 Correct 18 ms 39372 KB n=100
24 Correct 29 ms 39372 KB n=100
25 Correct 21 ms 39396 KB n=100
26 Correct 18 ms 39464 KB n=12
27 Correct 18 ms 39408 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39372 KB n=5
2 Correct 19 ms 39372 KB n=100
3 Correct 18 ms 39436 KB n=100
4 Correct 17 ms 39372 KB n=100
5 Correct 17 ms 39372 KB n=100
6 Correct 17 ms 39420 KB n=100
7 Correct 18 ms 39372 KB n=100
8 Correct 18 ms 39436 KB n=100
9 Correct 18 ms 39364 KB n=100
10 Correct 17 ms 39372 KB n=100
11 Correct 17 ms 39468 KB n=100
12 Correct 24 ms 39440 KB n=100
13 Correct 18 ms 39388 KB n=100
14 Correct 18 ms 39412 KB n=100
15 Correct 20 ms 39364 KB n=100
16 Correct 19 ms 39440 KB n=100
17 Correct 18 ms 39372 KB n=100
18 Correct 19 ms 39484 KB n=100
19 Correct 18 ms 39372 KB n=100
20 Correct 18 ms 39440 KB n=100
21 Correct 20 ms 39440 KB n=100
22 Correct 18 ms 39408 KB n=100
23 Correct 18 ms 39372 KB n=100
24 Correct 29 ms 39372 KB n=100
25 Correct 21 ms 39396 KB n=100
26 Correct 18 ms 39464 KB n=12
27 Correct 18 ms 39408 KB n=100
28 Correct 21 ms 39548 KB n=500
29 Correct 21 ms 39500 KB n=500
30 Correct 18 ms 39476 KB n=500
31 Correct 25 ms 39492 KB n=500
32 Correct 25 ms 39504 KB n=500
33 Correct 18 ms 39500 KB n=500
34 Correct 18 ms 39468 KB n=500
35 Correct 19 ms 39476 KB n=500
36 Correct 21 ms 39500 KB n=500
37 Correct 19 ms 39500 KB n=500
38 Correct 22 ms 39468 KB n=500
39 Correct 24 ms 39500 KB n=500
40 Correct 18 ms 39500 KB n=500
41 Correct 18 ms 39492 KB n=500
42 Correct 18 ms 39500 KB n=500
43 Correct 18 ms 39508 KB n=500
44 Correct 23 ms 39492 KB n=500
45 Correct 24 ms 39500 KB n=500
46 Correct 19 ms 39476 KB n=500
47 Correct 18 ms 39456 KB n=500
48 Correct 19 ms 39456 KB n=500
49 Correct 18 ms 39560 KB n=500
50 Correct 19 ms 39488 KB n=500
51 Correct 18 ms 39464 KB n=500
52 Correct 19 ms 39500 KB n=500
53 Correct 24 ms 39496 KB n=500
54 Correct 19 ms 39544 KB n=500
55 Correct 18 ms 39492 KB n=278
56 Correct 18 ms 39500 KB n=500
57 Correct 18 ms 39500 KB n=500
58 Correct 18 ms 39500 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39372 KB n=5
2 Correct 19 ms 39372 KB n=100
3 Correct 18 ms 39436 KB n=100
4 Correct 17 ms 39372 KB n=100
5 Correct 17 ms 39372 KB n=100
6 Correct 17 ms 39420 KB n=100
7 Correct 18 ms 39372 KB n=100
8 Correct 18 ms 39436 KB n=100
9 Correct 18 ms 39364 KB n=100
10 Correct 17 ms 39372 KB n=100
11 Correct 17 ms 39468 KB n=100
12 Correct 24 ms 39440 KB n=100
13 Correct 18 ms 39388 KB n=100
14 Correct 18 ms 39412 KB n=100
15 Correct 20 ms 39364 KB n=100
16 Correct 19 ms 39440 KB n=100
17 Correct 18 ms 39372 KB n=100
18 Correct 19 ms 39484 KB n=100
19 Correct 18 ms 39372 KB n=100
20 Correct 18 ms 39440 KB n=100
21 Correct 20 ms 39440 KB n=100
22 Correct 18 ms 39408 KB n=100
23 Correct 18 ms 39372 KB n=100
24 Correct 29 ms 39372 KB n=100
25 Correct 21 ms 39396 KB n=100
26 Correct 18 ms 39464 KB n=12
27 Correct 18 ms 39408 KB n=100
28 Correct 21 ms 39548 KB n=500
29 Correct 21 ms 39500 KB n=500
30 Correct 18 ms 39476 KB n=500
31 Correct 25 ms 39492 KB n=500
32 Correct 25 ms 39504 KB n=500
33 Correct 18 ms 39500 KB n=500
34 Correct 18 ms 39468 KB n=500
35 Correct 19 ms 39476 KB n=500
36 Correct 21 ms 39500 KB n=500
37 Correct 19 ms 39500 KB n=500
38 Correct 22 ms 39468 KB n=500
39 Correct 24 ms 39500 KB n=500
40 Correct 18 ms 39500 KB n=500
41 Correct 18 ms 39492 KB n=500
42 Correct 18 ms 39500 KB n=500
43 Correct 18 ms 39508 KB n=500
44 Correct 23 ms 39492 KB n=500
45 Correct 24 ms 39500 KB n=500
46 Correct 19 ms 39476 KB n=500
47 Correct 18 ms 39456 KB n=500
48 Correct 19 ms 39456 KB n=500
49 Correct 18 ms 39560 KB n=500
50 Correct 19 ms 39488 KB n=500
51 Correct 18 ms 39464 KB n=500
52 Correct 19 ms 39500 KB n=500
53 Correct 24 ms 39496 KB n=500
54 Correct 19 ms 39544 KB n=500
55 Correct 18 ms 39492 KB n=278
56 Correct 18 ms 39500 KB n=500
57 Correct 18 ms 39500 KB n=500
58 Correct 18 ms 39500 KB n=500
59 Correct 21 ms 39720 KB n=2000
60 Correct 26 ms 39876 KB n=2000
61 Correct 23 ms 39756 KB n=2000
62 Correct 29 ms 39708 KB n=2000
63 Correct 21 ms 39756 KB n=2000
64 Correct 22 ms 39756 KB n=2000
65 Correct 21 ms 39732 KB n=2000
66 Correct 22 ms 39748 KB n=2000
67 Correct 26 ms 39756 KB n=2000
68 Correct 25 ms 39756 KB n=2000
69 Correct 23 ms 39748 KB n=2000
70 Correct 22 ms 39728 KB n=2000
71 Correct 25 ms 39780 KB n=2000
72 Correct 23 ms 39672 KB n=2000
73 Correct 23 ms 39756 KB n=2000
74 Correct 21 ms 39724 KB n=1844
75 Correct 24 ms 39756 KB n=2000
76 Correct 22 ms 39732 KB n=2000
77 Correct 21 ms 39756 KB n=2000
78 Correct 20 ms 39728 KB n=2000
79 Correct 22 ms 39756 KB n=2000
80 Correct 23 ms 39824 KB n=2000
81 Correct 22 ms 39808 KB n=2000
82 Correct 24 ms 39748 KB n=2000
83 Correct 23 ms 39816 KB n=2000
84 Correct 22 ms 39716 KB n=2000
85 Correct 24 ms 39812 KB n=2000
86 Correct 24 ms 39756 KB n=2000
87 Correct 25 ms 39784 KB n=2000
88 Correct 22 ms 39808 KB n=2000
89 Correct 25 ms 39788 KB n=2000
90 Correct 22 ms 39876 KB n=2000
91 Correct 30 ms 39736 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39372 KB n=5
2 Correct 19 ms 39372 KB n=100
3 Correct 18 ms 39436 KB n=100
4 Correct 17 ms 39372 KB n=100
5 Correct 17 ms 39372 KB n=100
6 Correct 17 ms 39420 KB n=100
7 Correct 18 ms 39372 KB n=100
8 Correct 18 ms 39436 KB n=100
9 Correct 18 ms 39364 KB n=100
10 Correct 17 ms 39372 KB n=100
11 Correct 17 ms 39468 KB n=100
12 Correct 24 ms 39440 KB n=100
13 Correct 18 ms 39388 KB n=100
14 Correct 18 ms 39412 KB n=100
15 Correct 20 ms 39364 KB n=100
16 Correct 19 ms 39440 KB n=100
17 Correct 18 ms 39372 KB n=100
18 Correct 19 ms 39484 KB n=100
19 Correct 18 ms 39372 KB n=100
20 Correct 18 ms 39440 KB n=100
21 Correct 20 ms 39440 KB n=100
22 Correct 18 ms 39408 KB n=100
23 Correct 18 ms 39372 KB n=100
24 Correct 29 ms 39372 KB n=100
25 Correct 21 ms 39396 KB n=100
26 Correct 18 ms 39464 KB n=12
27 Correct 18 ms 39408 KB n=100
28 Correct 21 ms 39548 KB n=500
29 Correct 21 ms 39500 KB n=500
30 Correct 18 ms 39476 KB n=500
31 Correct 25 ms 39492 KB n=500
32 Correct 25 ms 39504 KB n=500
33 Correct 18 ms 39500 KB n=500
34 Correct 18 ms 39468 KB n=500
35 Correct 19 ms 39476 KB n=500
36 Correct 21 ms 39500 KB n=500
37 Correct 19 ms 39500 KB n=500
38 Correct 22 ms 39468 KB n=500
39 Correct 24 ms 39500 KB n=500
40 Correct 18 ms 39500 KB n=500
41 Correct 18 ms 39492 KB n=500
42 Correct 18 ms 39500 KB n=500
43 Correct 18 ms 39508 KB n=500
44 Correct 23 ms 39492 KB n=500
45 Correct 24 ms 39500 KB n=500
46 Correct 19 ms 39476 KB n=500
47 Correct 18 ms 39456 KB n=500
48 Correct 19 ms 39456 KB n=500
49 Correct 18 ms 39560 KB n=500
50 Correct 19 ms 39488 KB n=500
51 Correct 18 ms 39464 KB n=500
52 Correct 19 ms 39500 KB n=500
53 Correct 24 ms 39496 KB n=500
54 Correct 19 ms 39544 KB n=500
55 Correct 18 ms 39492 KB n=278
56 Correct 18 ms 39500 KB n=500
57 Correct 18 ms 39500 KB n=500
58 Correct 18 ms 39500 KB n=500
59 Correct 21 ms 39720 KB n=2000
60 Correct 26 ms 39876 KB n=2000
61 Correct 23 ms 39756 KB n=2000
62 Correct 29 ms 39708 KB n=2000
63 Correct 21 ms 39756 KB n=2000
64 Correct 22 ms 39756 KB n=2000
65 Correct 21 ms 39732 KB n=2000
66 Correct 22 ms 39748 KB n=2000
67 Correct 26 ms 39756 KB n=2000
68 Correct 25 ms 39756 KB n=2000
69 Correct 23 ms 39748 KB n=2000
70 Correct 22 ms 39728 KB n=2000
71 Correct 25 ms 39780 KB n=2000
72 Correct 23 ms 39672 KB n=2000
73 Correct 23 ms 39756 KB n=2000
74 Correct 21 ms 39724 KB n=1844
75 Correct 24 ms 39756 KB n=2000
76 Correct 22 ms 39732 KB n=2000
77 Correct 21 ms 39756 KB n=2000
78 Correct 20 ms 39728 KB n=2000
79 Correct 22 ms 39756 KB n=2000
80 Correct 23 ms 39824 KB n=2000
81 Correct 22 ms 39808 KB n=2000
82 Correct 24 ms 39748 KB n=2000
83 Correct 23 ms 39816 KB n=2000
84 Correct 22 ms 39716 KB n=2000
85 Correct 24 ms 39812 KB n=2000
86 Correct 24 ms 39756 KB n=2000
87 Correct 25 ms 39784 KB n=2000
88 Correct 22 ms 39808 KB n=2000
89 Correct 25 ms 39788 KB n=2000
90 Correct 22 ms 39876 KB n=2000
91 Correct 30 ms 39736 KB n=2000
92 Correct 783 ms 74516 KB n=200000
93 Correct 1120 ms 80108 KB n=200000
94 Correct 1064 ms 84816 KB n=200000
95 Correct 827 ms 74320 KB n=200000
96 Correct 759 ms 74312 KB n=200000
97 Correct 1120 ms 78944 KB n=200000
98 Correct 776 ms 74292 KB n=200000
99 Correct 987 ms 74524 KB n=200000
100 Correct 807 ms 74484 KB n=200000
101 Correct 1094 ms 86444 KB n=200000
102 Correct 635 ms 75492 KB n=200000
103 Correct 640 ms 75516 KB n=200000
104 Correct 696 ms 75728 KB n=200000
105 Correct 640 ms 75956 KB n=200000
106 Correct 680 ms 75860 KB n=200000
107 Correct 686 ms 75964 KB n=200000
108 Correct 851 ms 74368 KB n=200000
109 Correct 852 ms 74544 KB n=200000
110 Correct 861 ms 74332 KB n=200000
111 Correct 865 ms 73848 KB n=200000
112 Correct 1058 ms 85000 KB n=200000
113 Correct 1151 ms 78916 KB n=200000
114 Correct 782 ms 74008 KB n=200000
115 Correct 1197 ms 76244 KB n=200000
116 Correct 746 ms 74544 KB n=200000
117 Correct 1057 ms 85528 KB n=200000
118 Correct 1155 ms 77500 KB n=200000
119 Correct 742 ms 74544 KB n=200000
120 Correct 1037 ms 85252 KB n=200000
121 Correct 1152 ms 85416 KB n=200000
122 Correct 1134 ms 85552 KB n=200000
123 Correct 711 ms 75728 KB n=200000
124 Correct 264 ms 52332 KB n=25264