oj.uz

Submission #202653

# Submission time Handle Problem Language Result Execution time Memory
202653 2020-02-17T15:20:54 Z quocnguyen1012 Birthday gift (IZhO18_treearray) C++14
100 / 100
 1625 ms 74940 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 5;

vector<int> adj[maxn];
int N, M, Q;
int a[maxn], depth[maxn], par[maxn][20];
set<pair<int, int>> can[maxn];

void prepare(int u, int p = -1)
{
  for (int i = 1; (1 << i) <= N; ++i)
    par[u][i] = par[par[u][i - 1]][i - 1];
  for (int v : adj[u]) if (v != p){
    depth[v] = depth[u] + 1;
    par[v][0] = u;
    prepare(v, u);
  }
}

int LCA(int x, int y)
{
  if (depth[x] < depth[y]) swap(x, y);
  for (int k = 19; k >= 0; --k){
    if (depth[par[x][k]] >= depth[y]){
      x = par[x][k];
    }
  }
  if (x == y) return x;
  for (int k = 19; k >= 0; --k){
    if (par[x][k] != par[y][k]){
      x = par[x][k];
      y = par[y][k];
    }
  }
  return par[x][0];
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> M >> Q;
  for (int i = 1; i < N; ++i){
    int u, v; cin >> u >> v;
    adj[u].pb(v); adj[v].pb(u);
  }
  depth[1] = 1;
  prepare(1);
  for (int i = 1; i <= M; ++i){
    cin >> a[i];
    can[a[i]].insert(mp(i, i));
    if (i > 1){
      can[LCA(a[i], a[i - 1])].insert(mp(i - 1, i));
    }
  }
  while (Q--){
    int type; cin >> type;
    if (type == 1){
      int i, v; cin >> i >> v;
      can[a[i]].erase(mp(i, i));
      if (i > 1) can[LCA(a[i], a[i - 1])].erase(mp(i - 1, i));
      if (i < M) can[LCA(a[i], a[i + 1])].erase(mp(i, i + 1));
      a[i] = v;
      can[a[i]].insert(mp(i, i));
      if (i > 1) can[LCA(a[i], a[i - 1])].insert(mp(i - 1, i));
      if (i < M) can[LCA(a[i], a[i + 1])].insert(mp(i, i + 1));
    }
    else{
      int L, R, v; cin >> L >> R >> v;
      auto it = can[v].lower_bound(mp(L, 0));
      int l = -1, r = -1;
      if (it != can[v].end() && it -> se <= R){
        l = it -> fi;
        r = it -> se;
      }
      cout << l << ' ' << r << '\n';
    }
  }
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
treearray.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB n=5
2 Correct 14 ms 14456 KB n=100
3 Correct 14 ms 14332 KB n=100
4 Correct 15 ms 14456 KB n=100
5 Correct 14 ms 14456 KB n=100
6 Correct 14 ms 14456 KB n=100
7 Correct 14 ms 14456 KB n=100
8 Correct 14 ms 14456 KB n=100
9 Correct 15 ms 14456 KB n=100
10 Correct 14 ms 14456 KB n=100
11 Correct 14 ms 14456 KB n=100
12 Correct 14 ms 14456 KB n=100
13 Correct 14 ms 14456 KB n=100
14 Correct 14 ms 14456 KB n=100
15 Correct 14 ms 14460 KB n=100
16 Correct 14 ms 14456 KB n=100
17 Correct 14 ms 14456 KB n=100
18 Correct 14 ms 14456 KB n=100
19 Correct 14 ms 14456 KB n=100
20 Correct 14 ms 14456 KB n=100
21 Correct 14 ms 14456 KB n=100
22 Correct 14 ms 14456 KB n=100
23 Correct 15 ms 14456 KB n=100
24 Correct 14 ms 14460 KB n=100
25 Correct 14 ms 14456 KB n=100
26 Correct 14 ms 14456 KB n=12
27 Correct 14 ms 14456 KB n=100
28 Correct 15 ms 14584 KB n=500
29 Correct 15 ms 14584 KB n=500
30 Correct 17 ms 14584 KB n=500
31 Correct 11 ms 14588 KB n=500
32 Correct 15 ms 14584 KB n=500
33 Correct 15 ms 14584 KB n=500
34 Correct 15 ms 14584 KB n=500
35 Correct 15 ms 14584 KB n=500
36 Correct 16 ms 14584 KB n=500
37 Correct 14 ms 14584 KB n=500
38 Correct 15 ms 14584 KB n=500
39 Correct 15 ms 14584 KB n=500
40 Correct 15 ms 14584 KB n=500
41 Correct 15 ms 14584 KB n=500
42 Correct 15 ms 14584 KB n=500
43 Correct 15 ms 14584 KB n=500
44 Correct 15 ms 14584 KB n=500
45 Correct 15 ms 14584 KB n=500
46 Correct 15 ms 14584 KB n=500
47 Correct 15 ms 14584 KB n=500
48 Correct 15 ms 14584 KB n=500
49 Correct 15 ms 14588 KB n=500
50 Correct 15 ms 14584 KB n=500
51 Correct 15 ms 14584 KB n=500
52 Correct 14 ms 14584 KB n=500
53 Correct 16 ms 14584 KB n=500
54 Correct 15 ms 14584 KB n=500
55 Correct 15 ms 14584 KB n=278
56 Correct 15 ms 14584 KB n=500
57 Correct 15 ms 14584 KB n=500
58 Correct 15 ms 14584 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB n=5
2 Correct 14 ms 14456 KB n=100
3 Correct 14 ms 14332 KB n=100
4 Correct 15 ms 14456 KB n=100
5 Correct 14 ms 14456 KB n=100
6 Correct 14 ms 14456 KB n=100
7 Correct 14 ms 14456 KB n=100
8 Correct 14 ms 14456 KB n=100
9 Correct 15 ms 14456 KB n=100
10 Correct 14 ms 14456 KB n=100
11 Correct 14 ms 14456 KB n=100
12 Correct 14 ms 14456 KB n=100
13 Correct 14 ms 14456 KB n=100
14 Correct 14 ms 14456 KB n=100
15 Correct 14 ms 14460 KB n=100
16 Correct 14 ms 14456 KB n=100
17 Correct 14 ms 14456 KB n=100
18 Correct 14 ms 14456 KB n=100
19 Correct 14 ms 14456 KB n=100
20 Correct 14 ms 14456 KB n=100
21 Correct 14 ms 14456 KB n=100
22 Correct 14 ms 14456 KB n=100
23 Correct 15 ms 14456 KB n=100
24 Correct 14 ms 14460 KB n=100
25 Correct 14 ms 14456 KB n=100
26 Correct 14 ms 14456 KB n=12
27 Correct 14 ms 14456 KB n=100
28 Correct 15 ms 14584 KB n=500
29 Correct 15 ms 14584 KB n=500
30 Correct 17 ms 14584 KB n=500
31 Correct 11 ms 14588 KB n=500
32 Correct 15 ms 14584 KB n=500
33 Correct 15 ms 14584 KB n=500
34 Correct 15 ms 14584 KB n=500
35 Correct 15 ms 14584 KB n=500
36 Correct 16 ms 14584 KB n=500
37 Correct 14 ms 14584 KB n=500
38 Correct 15 ms 14584 KB n=500
39 Correct 15 ms 14584 KB n=500
40 Correct 15 ms 14584 KB n=500
41 Correct 15 ms 14584 KB n=500
42 Correct 15 ms 14584 KB n=500
43 Correct 15 ms 14584 KB n=500
44 Correct 15 ms 14584 KB n=500
45 Correct 15 ms 14584 KB n=500
46 Correct 15 ms 14584 KB n=500
47 Correct 15 ms 14584 KB n=500
48 Correct 15 ms 14584 KB n=500
49 Correct 15 ms 14588 KB n=500
50 Correct 15 ms 14584 KB n=500
51 Correct 15 ms 14584 KB n=500
52 Correct 14 ms 14584 KB n=500
53 Correct 16 ms 14584 KB n=500
54 Correct 15 ms 14584 KB n=500
55 Correct 15 ms 14584 KB n=278
56 Correct 15 ms 14584 KB n=500
57 Correct 15 ms 14584 KB n=500
58 Correct 15 ms 14584 KB n=500
59 Correct 19 ms 14968 KB n=2000
60 Correct 18 ms 15096 KB n=2000
61 Correct 19 ms 14968 KB n=2000
62 Correct 19 ms 14968 KB n=2000
63 Correct 19 ms 14968 KB n=2000
64 Correct 19 ms 14968 KB n=2000
65 Correct 18 ms 14968 KB n=2000
66 Correct 18 ms 14972 KB n=2000
67 Correct 19 ms 14968 KB n=2000
68 Correct 19 ms 14968 KB n=2000
69 Correct 20 ms 15096 KB n=2000
70 Correct 17 ms 14968 KB n=2000
71 Correct 17 ms 14968 KB n=2000
72 Correct 17 ms 14968 KB n=2000
73 Correct 17 ms 14968 KB n=2000
74 Correct 18 ms 14968 KB n=1844
75 Correct 19 ms 15096 KB n=2000
76 Correct 19 ms 14968 KB n=2000
77 Correct 19 ms 14968 KB n=2000
78 Correct 20 ms 14972 KB n=2000
79 Correct 18 ms 14968 KB n=2000
80 Correct 19 ms 14968 KB n=2000
81 Correct 19 ms 15100 KB n=2000
82 Correct 19 ms 14968 KB n=2000
83 Correct 20 ms 15096 KB n=2000
84 Correct 19 ms 14968 KB n=2000
85 Correct 19 ms 14968 KB n=2000
86 Correct 18 ms 14968 KB n=2000
87 Correct 18 ms 14968 KB n=2000
88 Correct 18 ms 14968 KB n=2000
89 Correct 19 ms 14968 KB n=2000
90 Correct 18 ms 15096 KB n=2000
91 Correct 18 ms 14968 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB n=5
2 Correct 14 ms 14456 KB n=100
3 Correct 14 ms 14332 KB n=100
4 Correct 15 ms 14456 KB n=100
5 Correct 14 ms 14456 KB n=100
6 Correct 14 ms 14456 KB n=100
7 Correct 14 ms 14456 KB n=100
8 Correct 14 ms 14456 KB n=100
9 Correct 15 ms 14456 KB n=100
10 Correct 14 ms 14456 KB n=100
11 Correct 14 ms 14456 KB n=100
12 Correct 14 ms 14456 KB n=100
13 Correct 14 ms 14456 KB n=100
14 Correct 14 ms 14456 KB n=100
15 Correct 14 ms 14460 KB n=100
16 Correct 14 ms 14456 KB n=100
17 Correct 14 ms 14456 KB n=100
18 Correct 14 ms 14456 KB n=100
19 Correct 14 ms 14456 KB n=100
20 Correct 14 ms 14456 KB n=100
21 Correct 14 ms 14456 KB n=100
22 Correct 14 ms 14456 KB n=100
23 Correct 15 ms 14456 KB n=100
24 Correct 14 ms 14460 KB n=100
25 Correct 14 ms 14456 KB n=100
26 Correct 14 ms 14456 KB n=12
27 Correct 14 ms 14456 KB n=100
28 Correct 15 ms 14584 KB n=500
29 Correct 15 ms 14584 KB n=500
30 Correct 17 ms 14584 KB n=500
31 Correct 11 ms 14588 KB n=500
32 Correct 15 ms 14584 KB n=500
33 Correct 15 ms 14584 KB n=500
34 Correct 15 ms 14584 KB n=500
35 Correct 15 ms 14584 KB n=500
36 Correct 16 ms 14584 KB n=500
37 Correct 14 ms 14584 KB n=500
38 Correct 15 ms 14584 KB n=500
39 Correct 15 ms 14584 KB n=500
40 Correct 15 ms 14584 KB n=500
41 Correct 15 ms 14584 KB n=500
42 Correct 15 ms 14584 KB n=500
43 Correct 15 ms 14584 KB n=500
44 Correct 15 ms 14584 KB n=500
45 Correct 15 ms 14584 KB n=500
46 Correct 15 ms 14584 KB n=500
47 Correct 15 ms 14584 KB n=500
48 Correct 15 ms 14584 KB n=500
49 Correct 15 ms 14588 KB n=500
50 Correct 15 ms 14584 KB n=500
51 Correct 15 ms 14584 KB n=500
52 Correct 14 ms 14584 KB n=500
53 Correct 16 ms 14584 KB n=500
54 Correct 15 ms 14584 KB n=500
55 Correct 15 ms 14584 KB n=278
56 Correct 15 ms 14584 KB n=500
57 Correct 15 ms 14584 KB n=500
58 Correct 15 ms 14584 KB n=500
59 Correct 19 ms 14968 KB n=2000
60 Correct 18 ms 15096 KB n=2000
61 Correct 19 ms 14968 KB n=2000
62 Correct 19 ms 14968 KB n=2000
63 Correct 19 ms 14968 KB n=2000
64 Correct 19 ms 14968 KB n=2000
65 Correct 18 ms 14968 KB n=2000
66 Correct 18 ms 14972 KB n=2000
67 Correct 19 ms 14968 KB n=2000
68 Correct 19 ms 14968 KB n=2000
69 Correct 20 ms 15096 KB n=2000
70 Correct 17 ms 14968 KB n=2000
71 Correct 17 ms 14968 KB n=2000
72 Correct 17 ms 14968 KB n=2000
73 Correct 17 ms 14968 KB n=2000
74 Correct 18 ms 14968 KB n=1844
75 Correct 19 ms 15096 KB n=2000
76 Correct 19 ms 14968 KB n=2000
77 Correct 19 ms 14968 KB n=2000
78 Correct 20 ms 14972 KB n=2000
79 Correct 18 ms 14968 KB n=2000
80 Correct 19 ms 14968 KB n=2000
81 Correct 19 ms 15100 KB n=2000
82 Correct 19 ms 14968 KB n=2000
83 Correct 20 ms 15096 KB n=2000
84 Correct 19 ms 14968 KB n=2000
85 Correct 19 ms 14968 KB n=2000
86 Correct 18 ms 14968 KB n=2000
87 Correct 18 ms 14968 KB n=2000
88 Correct 18 ms 14968 KB n=2000
89 Correct 19 ms 14968 KB n=2000
90 Correct 18 ms 15096 KB n=2000
91 Correct 18 ms 14968 KB n=2000
92 Correct 979 ms 65256 KB n=200000
93 Correct 1466 ms 70136 KB n=200000
94 Correct 1412 ms 73540 KB n=200000
95 Correct 937 ms 65200 KB n=200000
96 Correct 954 ms 64996 KB n=200000
97 Correct 1493 ms 69412 KB n=200000
98 Correct 931 ms 65128 KB n=200000
99 Correct 1231 ms 65456 KB n=200000
100 Correct 957 ms 65196 KB n=200000
101 Correct 1406 ms 74940 KB n=200000
102 Correct 582 ms 66168 KB n=200000
103 Correct 574 ms 66300 KB n=200000
104 Correct 578 ms 66296 KB n=200000
105 Correct 585 ms 66704 KB n=200000
106 Correct 612 ms 66632 KB n=200000
107 Correct 580 ms 66680 KB n=200000
108 Correct 1096 ms 65144 KB n=200000
109 Correct 1119 ms 65276 KB n=200000
110 Correct 1133 ms 65232 KB n=200000
111 Correct 934 ms 64564 KB n=200000
112 Correct 1488 ms 73736 KB n=200000
113 Correct 1516 ms 69372 KB n=200000
114 Correct 979 ms 64732 KB n=200000
115 Correct 1625 ms 67220 KB n=200000
116 Correct 891 ms 65236 KB n=200000
117 Correct 1426 ms 74232 KB n=200000
118 Correct 1549 ms 68216 KB n=200000
119 Correct 894 ms 65256 KB n=200000
120 Correct 1364 ms 73780 KB n=200000
121 Correct 1367 ms 73780 KB n=200000
122 Correct 1357 ms 74104 KB n=200000
123 Correct 653 ms 66424 KB n=200000
124 Correct 306 ms 29532 KB n=25264