oj.uz

Submission #341238

# Submission time Handle Problem Language Result Execution time Memory
341238 2020-12-29T09:29:36 Z IZhO_2021_I_want_Silver Birthday gift (IZhO18_treearray) C++14
100 / 100
 1255 ms 84276 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <stack>
#include <queue>
#include <deque>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>-

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

// template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//  order_of_key (k) : Number of items strictly smaller than k .
//  find_by_order(k) : K-th element in a set (counting from zero).
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define show(a) cerr << #a <<" -> "<< a <<" "
#define nl cerr <<"\n"
//#define int ll

const int N = 2e5 + 5;
const int oo = 1e9 + 5;
const int LG = 18;

int n, m, q, arr[N];
vector <int> g[N];
int par[N][LG+1], tin[N], tout[N], tiktak;
set <int> st1[N], st2[N];

void dfs(int v, int pr) {
    par[v][0] = pr;
    for (int i = 1; i <= LG; ++i) { par[v][i] = par[par[v][i-1]][i-1]; }

    tin[v] = ++tiktak;
    for (int to : g[v]) {
        if (to == pr) { continue; }
        dfs(to, v);
    }
    tout[v] = ++tiktak;
}

bool is_parent(int a, int b) {
    return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}

int lca(int a, int b) {
    if (is_parent(a, b)) { return a; }
    if (is_parent(b, a)) { return b; }
    for (int i = LG; i >= 0; --i) {
        if (!is_parent(par[a][i], b)) {
            a = par[a][i];
        }
    }
    return par[a][0];
}

/*void Print() {
    for (int v = 1; v <= n; ++v) {
        show(v); nl;
        for (int pos1 : st1[v]) { show(pos1); } nl;
        for (int pos2 : st2[v]) { show(pos2); } nl; nl;
    }
}*/

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    for (int i = 1; i <= m; ++i) {
        cin >> arr[i];
    }
    dfs(1, 1);
    for (int i = 1; i <= m; ++i) {
        st1[arr[i]].insert(i);
        if (i + 1 <= m) { st2[lca(arr[i], arr[i+1])].insert(i); }
    }
    for (int i = 1; i <= q; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, v;
            cin >> pos >> v;

            st1[arr[pos]].erase(pos);
            if (pos - 1 >= 1) { st2[lca(arr[pos-1], arr[pos])].erase(pos-1); }
            if (pos + 1 <= m) { st2[lca(arr[pos], arr[pos+1])].erase(pos); }

            arr[pos] = v;

            st1[arr[pos]].insert(pos);
            if (pos - 1 >= 1) { st2[lca(arr[pos-1], arr[pos])].insert(pos-1); }
            if (pos + 1 <= m) { st2[lca(arr[pos], arr[pos+1])].insert(pos); }

        }
        else {
            int l, r, v;
            cin >> l >> r >> v;

            auto it1 = st1[v].lower_bound(l);
            if (it1 != st1[v].end() && *it1 <= r) { cout << *it1 <<" "<< *it1 <<"\n"; continue; }

            auto it2 = st2[v].lower_bound(l);
            if (it2 != st2[v].end() && *it2 < r) { cout << *it2 <<" "<< *it2 + 1 <<"\n"; continue; }

            cout << -1 <<" "<< -1 <<"\n";
        }
    }
}

 main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tests = 1;
	//cin >> tests;
	while (tests --) {
		solve();
	}
	return 0;
}
/*
    Just Chalish!
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Compilation message

treearray.cpp:131:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  131 |  main () {
      |        ^

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23788 KB n=5
2 Correct 15 ms 23916 KB n=100
3 Correct 15 ms 23916 KB n=100
4 Correct 15 ms 23916 KB n=100
5 Correct 15 ms 23916 KB n=100
6 Correct 16 ms 23916 KB n=100
7 Correct 15 ms 23916 KB n=100
8 Correct 18 ms 23916 KB n=100
9 Correct 15 ms 24064 KB n=100
10 Correct 15 ms 23916 KB n=100
11 Correct 16 ms 23916 KB n=100
12 Correct 15 ms 23916 KB n=100
13 Correct 15 ms 23916 KB n=100
14 Correct 15 ms 23916 KB n=100
15 Correct 16 ms 23916 KB n=100
16 Correct 16 ms 23916 KB n=100
17 Correct 17 ms 23916 KB n=100
18 Correct 15 ms 23936 KB n=100
19 Correct 16 ms 23916 KB n=100
20 Correct 15 ms 23916 KB n=100
21 Correct 15 ms 23916 KB n=100
22 Correct 15 ms 23916 KB n=100
23 Correct 15 ms 23916 KB n=100
24 Correct 16 ms 23916 KB n=100
25 Correct 16 ms 23936 KB n=100
26 Correct 15 ms 23788 KB n=12
27 Correct 16 ms 23916 KB n=100
28 Correct 17 ms 23916 KB n=500
29 Correct 16 ms 24044 KB n=500
30 Correct 17 ms 23916 KB n=500
31 Correct 16 ms 23916 KB n=500
32 Correct 19 ms 23916 KB n=500
33 Correct 19 ms 23916 KB n=500
34 Correct 16 ms 23916 KB n=500
35 Correct 16 ms 23916 KB n=500
36 Correct 17 ms 23916 KB n=500
37 Correct 16 ms 24044 KB n=500
38 Correct 16 ms 23916 KB n=500
39 Correct 16 ms 23916 KB n=500
40 Correct 16 ms 23916 KB n=500
41 Correct 17 ms 23916 KB n=500
42 Correct 17 ms 23916 KB n=500
43 Correct 16 ms 23916 KB n=500
44 Correct 16 ms 23916 KB n=500
45 Correct 16 ms 23916 KB n=500
46 Correct 16 ms 23916 KB n=500
47 Correct 16 ms 23916 KB n=500
48 Correct 16 ms 23916 KB n=500
49 Correct 16 ms 23916 KB n=500
50 Correct 17 ms 23916 KB n=500
51 Correct 16 ms 23916 KB n=500
52 Correct 16 ms 23916 KB n=500
53 Correct 17 ms 23916 KB n=500
54 Correct 16 ms 23916 KB n=500
55 Correct 15 ms 23916 KB n=278
56 Correct 16 ms 23916 KB n=500
57 Correct 18 ms 23916 KB n=500
58 Correct 17 ms 23916 KB n=500
59 Correct 19 ms 24300 KB n=2000
60 Correct 18 ms 24428 KB n=2000
61 Correct 21 ms 24428 KB n=2000
62 Correct 21 ms 24428 KB n=2000
63 Correct 20 ms 24300 KB n=2000
64 Correct 20 ms 24300 KB n=2000
65 Correct 20 ms 24428 KB n=2000
66 Correct 19 ms 24428 KB n=2000
67 Correct 20 ms 24300 KB n=2000
68 Correct 19 ms 24320 KB n=2000
69 Correct 19 ms 24320 KB n=2000
70 Correct 21 ms 24300 KB n=2000
71 Correct 19 ms 24300 KB n=2000
72 Correct 22 ms 24340 KB n=2000
73 Correct 18 ms 24300 KB n=2000
74 Correct 19 ms 24300 KB n=1844
75 Correct 18 ms 24300 KB n=2000
76 Correct 20 ms 24300 KB n=2000
77 Correct 20 ms 24300 KB n=2000
78 Correct 20 ms 24300 KB n=2000
79 Correct 20 ms 24300 KB n=2000
80 Correct 19 ms 24428 KB n=2000
81 Correct 19 ms 24428 KB n=2000
82 Correct 19 ms 24300 KB n=2000
83 Correct 19 ms 24428 KB n=2000
84 Correct 19 ms 24300 KB n=2000
85 Correct 19 ms 24300 KB n=2000
86 Correct 20 ms 24300 KB n=2000
87 Correct 19 ms 24300 KB n=2000
88 Correct 20 ms 24428 KB n=2000
89 Correct 19 ms 24428 KB n=2000
90 Correct 19 ms 24428 KB n=2000
91 Correct 19 ms 24300 KB n=2000
92 Correct 906 ms 68716 KB n=200000
93 Correct 988 ms 76116 KB n=200000
94 Correct 763 ms 82924 KB n=200000
95 Correct 926 ms 74444 KB n=200000
96 Correct 899 ms 74444 KB n=200000
97 Correct 1120 ms 78708 KB n=200000
98 Correct 929 ms 74464 KB n=200000
99 Correct 1068 ms 74948 KB n=200000
100 Correct 905 ms 74480 KB n=200000
101 Correct 650 ms 84276 KB n=200000
102 Correct 536 ms 75664 KB n=200000
103 Correct 529 ms 75628 KB n=200000
104 Correct 540 ms 75756 KB n=200000
105 Correct 566 ms 76140 KB n=200000
106 Correct 576 ms 76268 KB n=200000
107 Correct 537 ms 76168 KB n=200000
108 Correct 944 ms 74732 KB n=200000
109 Correct 942 ms 74560 KB n=200000
110 Correct 942 ms 74604 KB n=200000
111 Correct 862 ms 73956 KB n=200000
112 Correct 652 ms 83232 KB n=200000
113 Correct 989 ms 78572 KB n=200000
114 Correct 835 ms 73952 KB n=200000
115 Correct 1255 ms 76524 KB n=200000
116 Correct 789 ms 74592 KB n=200000
117 Correct 629 ms 83692 KB n=200000
118 Correct 1084 ms 77548 KB n=200000
119 Correct 811 ms 74592 KB n=200000
120 Correct 559 ms 83308 KB n=200000
121 Correct 567 ms 83052 KB n=200000
122 Correct 567 ms 83368 KB n=200000
123 Correct 530 ms 75884 KB n=200000
124 Correct 203 ms 38764 KB n=25264