oj.uz

Submission #695058

# Submission time Handle Problem Language Result Execution time Memory
695058 2023-02-04T17:14:40 Z Abrar_Al_Samit Birthday gift (IZhO18_treearray) C++17
56 / 100
 2942 ms 844 KB 
#include<bits/stdc++.h>
using namespace std;

const int nax = 2004;

vector<int>g[nax];

int n, m, q;
int a[nax];
int sp[nax][18];
int tt(0);
int st[nax], en[nax], dep[nax];
int tree[nax * 4];

bool anc(int x, int y) {
  return st[x]<=st[y] && en[x]>=en[y];
}
int getlca(int x, int y) {
  if(x==0) return y;
  if(y==0) return x;

  for(int j=17; j>=0; --j) {
    if(!anc(sp[x][j], y)) {
      x = sp[x][j];
    }
  }
  if(!anc(x, y)) x = sp[x][0];
  return x;
}
void DFS(int v, int par = 1) {
  dep[v] = 1+dep[par];
  st[v] = tt++;

  sp[v][0] = par;
  for(int j=1; j<18; ++j) {
    sp[v][j] = sp[sp[v][j-1]][j-1];
  }

  for(int u : g[v]) if(u!=par) {
    DFS(u, v);
  }
  en[v] = tt++;
}

void build(int l, int r, int v) {
  if(l==r) {
    tree[v] = a[l];
    return;
  }
  int mid = (l+r)/2;
  build(l, mid, v*2);
  build(mid+1, r, v*2+1);

  tree[v] = getlca(tree[v*2], tree[v*2+1]);
}
void upd(int l, int r, int i, int val, int v) {
  if(l==r) {
    tree[v] = val;
    return;
  }
  int mid = (l+r)/2;
  if(i<=mid) upd(l, mid, i, val, v*2);
  else upd(mid+1, r, i, val, v*2+1);
  tree[v] = getlca(tree[v*2], tree[v*2+1]);
}

int query(int l, int r, int L, int R, int v) {
  if(l>=L && r<=R) return tree[v];
  if(l>R || r<L) return 0;

  int mid = (l+r)/2;
  return getlca(query(l, mid, L, R, v*2), query(mid+1, r, L, R, v*2+1));
}
void PlayGround() {
  cin>>n>>m>>q;

  for(int i=1; i<n; ++i) {
    int u, v;
    cin>>u>>v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for(int i=1; i<=m; ++i) {
    cin>>a[i];
  }

  dep[1] = -1;
  DFS(1);
  build(1, m, 1);

  while(q--) {
    int t;
    cin>>t;
    if(t==1) {
      int pos, v;
      cin>>pos>>v;
      upd(1, m, pos, v, 1);
      a[pos] = v;
    } else {
      int l, r, v;
      cin>>l>>r>>v;

      int p0=l, p1=l;

      int x(-1), y(-1);

      int cur = a[l];
      while(p0<=r) {
        while(p1<r && dep[cur]>dep[v]) {
          ++p1;
          cur = getlca(cur, a[p1]);
        }
        if(cur==v) {
          x = p0, y = p1;
          break;
        }

        ++p0;
        if(p1<p0) ++p1;
        
        cur = query(1, m, p0, p1, 1);

        //cerr<<p0<<' '<<p1<<' '<<cur<<endl;
      }

      cout<<x<<' '<<y<<'\n';
    } 
  }


  // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB n=5
2 Correct 1 ms 340 KB n=100
3 Correct 1 ms 384 KB n=100
4 Correct 1 ms 340 KB n=100
5 Correct 1 ms 340 KB n=100
6 Correct 2 ms 412 KB n=100
7 Correct 2 ms 380 KB n=100
8 Correct 1 ms 340 KB n=100
9 Correct 1 ms 376 KB n=100
10 Correct 2 ms 340 KB n=100
11 Correct 1 ms 340 KB n=100
12 Correct 1 ms 384 KB n=100
13 Correct 2 ms 340 KB n=100
14 Correct 1 ms 380 KB n=100
15 Correct 1 ms 384 KB n=100
16 Correct 1 ms 340 KB n=100
17 Correct 1 ms 380 KB n=100
18 Correct 1 ms 340 KB n=100
19 Correct 1 ms 340 KB n=100
20 Correct 1 ms 340 KB n=100
21 Correct 1 ms 340 KB n=100
22 Correct 1 ms 340 KB n=100
23 Correct 3 ms 340 KB n=100
24 Correct 3 ms 380 KB n=100
25 Correct 2 ms 340 KB n=100
26 Correct 1 ms 340 KB n=12
27 Correct 1 ms 340 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB n=5
2 Correct 1 ms 340 KB n=100
3 Correct 1 ms 384 KB n=100
4 Correct 1 ms 340 KB n=100
5 Correct 1 ms 340 KB n=100
6 Correct 2 ms 412 KB n=100
7 Correct 2 ms 380 KB n=100
8 Correct 1 ms 340 KB n=100
9 Correct 1 ms 376 KB n=100
10 Correct 2 ms 340 KB n=100
11 Correct 1 ms 340 KB n=100
12 Correct 1 ms 384 KB n=100
13 Correct 2 ms 340 KB n=100
14 Correct 1 ms 380 KB n=100
15 Correct 1 ms 384 KB n=100
16 Correct 1 ms 340 KB n=100
17 Correct 1 ms 380 KB n=100
18 Correct 1 ms 340 KB n=100
19 Correct 1 ms 340 KB n=100
20 Correct 1 ms 340 KB n=100
21 Correct 1 ms 340 KB n=100
22 Correct 1 ms 340 KB n=100
23 Correct 3 ms 340 KB n=100
24 Correct 3 ms 380 KB n=100
25 Correct 2 ms 340 KB n=100
26 Correct 1 ms 340 KB n=12
27 Correct 1 ms 340 KB n=100
28 Correct 2 ms 396 KB n=500
29 Correct 8 ms 468 KB n=500
30 Correct 9 ms 396 KB n=500
31 Correct 8 ms 468 KB n=500
32 Correct 1 ms 468 KB n=500
33 Correct 7 ms 468 KB n=500
34 Correct 1 ms 384 KB n=500
35 Correct 10 ms 480 KB n=500
36 Correct 34 ms 464 KB n=500
37 Correct 29 ms 340 KB n=500
38 Correct 29 ms 464 KB n=500
39 Correct 17 ms 468 KB n=500
40 Correct 15 ms 476 KB n=500
41 Correct 20 ms 340 KB n=500
42 Correct 21 ms 440 KB n=500
43 Correct 17 ms 460 KB n=500
44 Correct 19 ms 468 KB n=500
45 Correct 2 ms 384 KB n=500
46 Correct 9 ms 432 KB n=500
47 Correct 8 ms 468 KB n=500
48 Correct 2 ms 384 KB n=500
49 Correct 6 ms 392 KB n=500
50 Correct 5 ms 392 KB n=500
51 Correct 9 ms 476 KB n=500
52 Correct 12 ms 468 KB n=500
53 Correct 9 ms 392 KB n=500
54 Correct 30 ms 468 KB n=500
55 Correct 2 ms 340 KB n=278
56 Correct 125 ms 468 KB n=500
57 Correct 124 ms 468 KB n=500
58 Correct 17 ms 476 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB n=5
2 Correct 1 ms 340 KB n=100
3 Correct 1 ms 384 KB n=100
4 Correct 1 ms 340 KB n=100
5 Correct 1 ms 340 KB n=100
6 Correct 2 ms 412 KB n=100
7 Correct 2 ms 380 KB n=100
8 Correct 1 ms 340 KB n=100
9 Correct 1 ms 376 KB n=100
10 Correct 2 ms 340 KB n=100
11 Correct 1 ms 340 KB n=100
12 Correct 1 ms 384 KB n=100
13 Correct 2 ms 340 KB n=100
14 Correct 1 ms 380 KB n=100
15 Correct 1 ms 384 KB n=100
16 Correct 1 ms 340 KB n=100
17 Correct 1 ms 380 KB n=100
18 Correct 1 ms 340 KB n=100
19 Correct 1 ms 340 KB n=100
20 Correct 1 ms 340 KB n=100
21 Correct 1 ms 340 KB n=100
22 Correct 1 ms 340 KB n=100
23 Correct 3 ms 340 KB n=100
24 Correct 3 ms 380 KB n=100
25 Correct 2 ms 340 KB n=100
26 Correct 1 ms 340 KB n=12
27 Correct 1 ms 340 KB n=100
28 Correct 2 ms 396 KB n=500
29 Correct 8 ms 468 KB n=500
30 Correct 9 ms 396 KB n=500
31 Correct 8 ms 468 KB n=500
32 Correct 1 ms 468 KB n=500
33 Correct 7 ms 468 KB n=500
34 Correct 1 ms 384 KB n=500
35 Correct 10 ms 480 KB n=500
36 Correct 34 ms 464 KB n=500
37 Correct 29 ms 340 KB n=500
38 Correct 29 ms 464 KB n=500
39 Correct 17 ms 468 KB n=500
40 Correct 15 ms 476 KB n=500
41 Correct 20 ms 340 KB n=500
42 Correct 21 ms 440 KB n=500
43 Correct 17 ms 460 KB n=500
44 Correct 19 ms 468 KB n=500
45 Correct 2 ms 384 KB n=500
46 Correct 9 ms 432 KB n=500
47 Correct 8 ms 468 KB n=500
48 Correct 2 ms 384 KB n=500
49 Correct 6 ms 392 KB n=500
50 Correct 5 ms 392 KB n=500
51 Correct 9 ms 476 KB n=500
52 Correct 12 ms 468 KB n=500
53 Correct 9 ms 392 KB n=500
54 Correct 30 ms 468 KB n=500
55 Correct 2 ms 340 KB n=278
56 Correct 125 ms 468 KB n=500
57 Correct 124 ms 468 KB n=500
58 Correct 17 ms 476 KB n=500
59 Correct 4 ms 696 KB n=2000
60 Correct 180 ms 752 KB n=2000
61 Correct 134 ms 724 KB n=2000
62 Correct 95 ms 688 KB n=2000
63 Correct 5 ms 648 KB n=2000
64 Correct 115 ms 596 KB n=2000
65 Correct 4 ms 596 KB n=2000
66 Correct 157 ms 732 KB n=2000
67 Correct 8 ms 644 KB n=2000
68 Correct 118 ms 724 KB n=2000
69 Correct 486 ms 664 KB n=2000
70 Correct 474 ms 680 KB n=2000
71 Correct 488 ms 792 KB n=2000
72 Correct 233 ms 672 KB n=2000
73 Correct 261 ms 664 KB n=2000
74 Correct 3 ms 596 KB n=1844
75 Correct 239 ms 668 KB n=2000
76 Correct 268 ms 676 KB n=2000
77 Correct 261 ms 668 KB n=2000
78 Correct 282 ms 664 KB n=2000
79 Correct 5 ms 596 KB n=2000
80 Correct 107 ms 624 KB n=2000
81 Correct 93 ms 704 KB n=2000
82 Correct 5 ms 620 KB n=2000
83 Correct 171 ms 728 KB n=2000
84 Correct 79 ms 676 KB n=2000
85 Correct 156 ms 692 KB n=2000
86 Correct 136 ms 688 KB n=2000
87 Correct 93 ms 596 KB n=2000
88 Correct 2942 ms 764 KB n=2000
89 Correct 2933 ms 844 KB n=2000
90 Correct 611 ms 756 KB n=2000
91 Correct 300 ms 684 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB n=5
2 Correct 1 ms 340 KB n=100
3 Correct 1 ms 384 KB n=100
4 Correct 1 ms 340 KB n=100
5 Correct 1 ms 340 KB n=100
6 Correct 2 ms 412 KB n=100
7 Correct 2 ms 380 KB n=100
8 Correct 1 ms 340 KB n=100
9 Correct 1 ms 376 KB n=100
10 Correct 2 ms 340 KB n=100
11 Correct 1 ms 340 KB n=100
12 Correct 1 ms 384 KB n=100
13 Correct 2 ms 340 KB n=100
14 Correct 1 ms 380 KB n=100
15 Correct 1 ms 384 KB n=100
16 Correct 1 ms 340 KB n=100
17 Correct 1 ms 380 KB n=100
18 Correct 1 ms 340 KB n=100
19 Correct 1 ms 340 KB n=100
20 Correct 1 ms 340 KB n=100
21 Correct 1 ms 340 KB n=100
22 Correct 1 ms 340 KB n=100
23 Correct 3 ms 340 KB n=100
24 Correct 3 ms 380 KB n=100
25 Correct 2 ms 340 KB n=100
26 Correct 1 ms 340 KB n=12
27 Correct 1 ms 340 KB n=100
28 Correct 2 ms 396 KB n=500
29 Correct 8 ms 468 KB n=500
30 Correct 9 ms 396 KB n=500
31 Correct 8 ms 468 KB n=500
32 Correct 1 ms 468 KB n=500
33 Correct 7 ms 468 KB n=500
34 Correct 1 ms 384 KB n=500
35 Correct 10 ms 480 KB n=500
36 Correct 34 ms 464 KB n=500
37 Correct 29 ms 340 KB n=500
38 Correct 29 ms 464 KB n=500
39 Correct 17 ms 468 KB n=500
40 Correct 15 ms 476 KB n=500
41 Correct 20 ms 340 KB n=500
42 Correct 21 ms 440 KB n=500
43 Correct 17 ms 460 KB n=500
44 Correct 19 ms 468 KB n=500
45 Correct 2 ms 384 KB n=500
46 Correct 9 ms 432 KB n=500
47 Correct 8 ms 468 KB n=500
48 Correct 2 ms 384 KB n=500
49 Correct 6 ms 392 KB n=500
50 Correct 5 ms 392 KB n=500
51 Correct 9 ms 476 KB n=500
52 Correct 12 ms 468 KB n=500
53 Correct 9 ms 392 KB n=500
54 Correct 30 ms 468 KB n=500
55 Correct 2 ms 340 KB n=278
56 Correct 125 ms 468 KB n=500
57 Correct 124 ms 468 KB n=500
58 Correct 17 ms 476 KB n=500
59 Correct 4 ms 696 KB n=2000
60 Correct 180 ms 752 KB n=2000
61 Correct 134 ms 724 KB n=2000
62 Correct 95 ms 688 KB n=2000
63 Correct 5 ms 648 KB n=2000
64 Correct 115 ms 596 KB n=2000
65 Correct 4 ms 596 KB n=2000
66 Correct 157 ms 732 KB n=2000
67 Correct 8 ms 644 KB n=2000
68 Correct 118 ms 724 KB n=2000
69 Correct 486 ms 664 KB n=2000
70 Correct 474 ms 680 KB n=2000
71 Correct 488 ms 792 KB n=2000
72 Correct 233 ms 672 KB n=2000
73 Correct 261 ms 664 KB n=2000
74 Correct 3 ms 596 KB n=1844
75 Correct 239 ms 668 KB n=2000
76 Correct 268 ms 676 KB n=2000
77 Correct 261 ms 668 KB n=2000
78 Correct 282 ms 664 KB n=2000
79 Correct 5 ms 596 KB n=2000
80 Correct 107 ms 624 KB n=2000
81 Correct 93 ms 704 KB n=2000
82 Correct 5 ms 620 KB n=2000
83 Correct 171 ms 728 KB n=2000
84 Correct 79 ms 676 KB n=2000
85 Correct 156 ms 692 KB n=2000
86 Correct 136 ms 688 KB n=2000
87 Correct 93 ms 596 KB n=2000
88 Correct 2942 ms 764 KB n=2000
89 Correct 2933 ms 844 KB n=2000
90 Correct 611 ms 756 KB n=2000
91 Correct 300 ms 684 KB n=2000
92 Runtime error 1 ms 596 KB Execution killed with signal 11
93 Halted 0 ms 0 KB -