oj.uz

Submission #610873

# Submission time Handle Problem Language Result Execution time Memory
610873 2022-07-28T16:54:46 Z Do_you_copy Birthday gift (IZhO18_treearray) C++17
100 / 100
 991 ms 84040 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 2e5 + 1;

int n, m, q;
int lift[maxN][20];
int depth[maxN];
int a[maxN];
vector <int> adj[maxN];
void dfs(int u, int p){
    lift[u][0] = p;
    for (int i = 1; i < 20; ++i){
        lift[u][i] = lift[lift[u][i - 1]][i - 1];
    }
    depth[u] = depth[p] + 1;
    for (int i: adj[u]){
        if (i == p) continue;
        dfs(i, u);
    }
}

int lca(int u, int v){
    if (depth[u] < depth[v]) swap(u, v);
    int k = depth[u] - depth[v];
    while (k){
        int t = k & -k;
        u = lift[u][__lg(t)];
        k ^= t;
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; --i){
        if (lift[u][i] != lift[v][i]){
            u = lift[u][i];
            v = lift[v][i];
        }
    }
    return lift[u][0];
}

set <int> S[maxN];
set <int> Q[maxN];
void Init(){
    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);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; ++i){
        cin >> a[i];
        Q[a[i]].insert(i);
    }
    for (int i = 1; i < m; ++i){
        int t = lca(a[i], a[i + 1]);
        S[t].insert(i);
    }
    while (q--){
        int t; cin >> t;
        if (t == 1){
            int pos, v;
            cin >> pos >> v;
            Q[a[pos]].erase(pos);
            Q[v].insert(pos);
            if (pos > 1 && pos < m){
                int l = lca(a[pos], a[pos - 1]);
                int r = lca(a[pos], a[pos + 1]);
                a[pos] = v;
                S[l].erase(pos - 1);
                S[r].erase(pos);
                l = lca(a[pos], a[pos - 1]);
                r = lca(a[pos], a[pos + 1]);
                S[l].insert(pos - 1);
                S[r].insert(pos);
            }
            if (pos == 1){
                int r = lca(a[pos], a[pos + 1]);
                a[pos] = v;
                S[r].erase(pos);
                r = lca(a[pos], a[pos + 1]);
                S[r].insert(pos);
            }
            if (pos == m){
                int l = lca(a[pos], a[pos - 1]);
                a[pos] = v;
                S[l].erase(pos - 1);
                l = lca(a[pos], a[pos - 1]);
                S[l].insert(pos - 1);
            }
        }
        else{
            int l, r, v;
            cin >> l >> r >> v;
            if (l == r){
                if (a[l] != v) cout << "-1 -1\n";
                else cout << l << " " << r << "\n";
            }
            else{
                auto k = S[v].lower_bound(l);
                if (k == S[v].end() || *k >= r){
                    auto kk = Q[v].lower_bound(l);
                    if (kk == Q[v].end() || *kk > r) cout << "-1 -1\n";
                    else cout << *kk << " " << *kk << "\n";
                }
                else cout << *k << " " << *k + 1 << "\n";
            }
        }
    }
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 11 ms 23800 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 18 ms 23824 KB n=100
6 Correct 15 ms 23824 KB n=100
7 Correct 13 ms 23852 KB n=100
8 Correct 18 ms 23816 KB n=100
9 Correct 13 ms 23820 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 15 ms 23796 KB n=100
13 Correct 15 ms 23820 KB n=100
14 Correct 13 ms 23764 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 14 ms 23844 KB n=100
17 Correct 13 ms 23776 KB n=100
18 Correct 13 ms 23764 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 13 ms 23768 KB n=100
21 Correct 12 ms 23764 KB n=100
22 Correct 16 ms 23836 KB n=100
23 Correct 13 ms 23764 KB n=100
24 Correct 16 ms 23764 KB n=100
25 Correct 15 ms 23792 KB n=100
26 Correct 18 ms 23816 KB n=12
27 Correct 16 ms 23820 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 11 ms 23800 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 18 ms 23824 KB n=100
6 Correct 15 ms 23824 KB n=100
7 Correct 13 ms 23852 KB n=100
8 Correct 18 ms 23816 KB n=100
9 Correct 13 ms 23820 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 15 ms 23796 KB n=100
13 Correct 15 ms 23820 KB n=100
14 Correct 13 ms 23764 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 14 ms 23844 KB n=100
17 Correct 13 ms 23776 KB n=100
18 Correct 13 ms 23764 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 13 ms 23768 KB n=100
21 Correct 12 ms 23764 KB n=100
22 Correct 16 ms 23836 KB n=100
23 Correct 13 ms 23764 KB n=100
24 Correct 16 ms 23764 KB n=100
25 Correct 15 ms 23792 KB n=100
26 Correct 18 ms 23816 KB n=12
27 Correct 16 ms 23820 KB n=100
28 Correct 14 ms 23880 KB n=500
29 Correct 17 ms 23892 KB n=500
30 Correct 14 ms 23960 KB n=500
31 Correct 17 ms 23892 KB n=500
32 Correct 17 ms 23920 KB n=500
33 Correct 14 ms 23900 KB n=500
34 Correct 17 ms 23960 KB n=500
35 Correct 16 ms 23960 KB n=500
36 Correct 14 ms 23848 KB n=500
37 Correct 13 ms 23948 KB n=500
38 Correct 13 ms 23960 KB n=500
39 Correct 14 ms 23892 KB n=500
40 Correct 17 ms 23852 KB n=500
41 Correct 18 ms 23964 KB n=500
42 Correct 17 ms 23892 KB n=500
43 Correct 14 ms 23892 KB n=500
44 Correct 14 ms 23856 KB n=500
45 Correct 15 ms 23892 KB n=500
46 Correct 14 ms 23960 KB n=500
47 Correct 14 ms 23892 KB n=500
48 Correct 14 ms 23892 KB n=500
49 Correct 17 ms 23892 KB n=500
50 Correct 17 ms 23948 KB n=500
51 Correct 16 ms 23952 KB n=500
52 Correct 17 ms 23896 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 17 ms 23864 KB n=500
55 Correct 15 ms 23892 KB n=278
56 Correct 16 ms 23872 KB n=500
57 Correct 13 ms 23892 KB n=500
58 Correct 18 ms 23920 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 11 ms 23800 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 18 ms 23824 KB n=100
6 Correct 15 ms 23824 KB n=100
7 Correct 13 ms 23852 KB n=100
8 Correct 18 ms 23816 KB n=100
9 Correct 13 ms 23820 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 15 ms 23796 KB n=100
13 Correct 15 ms 23820 KB n=100
14 Correct 13 ms 23764 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 14 ms 23844 KB n=100
17 Correct 13 ms 23776 KB n=100
18 Correct 13 ms 23764 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 13 ms 23768 KB n=100
21 Correct 12 ms 23764 KB n=100
22 Correct 16 ms 23836 KB n=100
23 Correct 13 ms 23764 KB n=100
24 Correct 16 ms 23764 KB n=100
25 Correct 15 ms 23792 KB n=100
26 Correct 18 ms 23816 KB n=12
27 Correct 16 ms 23820 KB n=100
28 Correct 14 ms 23880 KB n=500
29 Correct 17 ms 23892 KB n=500
30 Correct 14 ms 23960 KB n=500
31 Correct 17 ms 23892 KB n=500
32 Correct 17 ms 23920 KB n=500
33 Correct 14 ms 23900 KB n=500
34 Correct 17 ms 23960 KB n=500
35 Correct 16 ms 23960 KB n=500
36 Correct 14 ms 23848 KB n=500
37 Correct 13 ms 23948 KB n=500
38 Correct 13 ms 23960 KB n=500
39 Correct 14 ms 23892 KB n=500
40 Correct 17 ms 23852 KB n=500
41 Correct 18 ms 23964 KB n=500
42 Correct 17 ms 23892 KB n=500
43 Correct 14 ms 23892 KB n=500
44 Correct 14 ms 23856 KB n=500
45 Correct 15 ms 23892 KB n=500
46 Correct 14 ms 23960 KB n=500
47 Correct 14 ms 23892 KB n=500
48 Correct 14 ms 23892 KB n=500
49 Correct 17 ms 23892 KB n=500
50 Correct 17 ms 23948 KB n=500
51 Correct 16 ms 23952 KB n=500
52 Correct 17 ms 23896 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 17 ms 23864 KB n=500
55 Correct 15 ms 23892 KB n=278
56 Correct 16 ms 23872 KB n=500
57 Correct 13 ms 23892 KB n=500
58 Correct 18 ms 23920 KB n=500
59 Correct 16 ms 24276 KB n=2000
60 Correct 16 ms 24344 KB n=2000
61 Correct 16 ms 24276 KB n=2000
62 Correct 21 ms 24320 KB n=2000
63 Correct 16 ms 24264 KB n=2000
64 Correct 16 ms 24296 KB n=2000
65 Correct 16 ms 24216 KB n=2000
66 Correct 16 ms 24276 KB n=2000
67 Correct 18 ms 24200 KB n=2000
68 Correct 16 ms 24276 KB n=2000
69 Correct 15 ms 24276 KB n=2000
70 Correct 15 ms 24276 KB n=2000
71 Correct 15 ms 24276 KB n=2000
72 Correct 15 ms 24216 KB n=2000
73 Correct 15 ms 24252 KB n=2000
74 Correct 16 ms 24240 KB n=1844
75 Correct 16 ms 24216 KB n=2000
76 Correct 20 ms 24252 KB n=2000
77 Correct 18 ms 24276 KB n=2000
78 Correct 17 ms 24292 KB n=2000
79 Correct 17 ms 24276 KB n=2000
80 Correct 18 ms 24348 KB n=2000
81 Correct 16 ms 24272 KB n=2000
82 Correct 21 ms 24204 KB n=2000
83 Correct 19 ms 24348 KB n=2000
84 Correct 16 ms 24276 KB n=2000
85 Correct 16 ms 24244 KB n=2000
86 Correct 16 ms 24276 KB n=2000
87 Correct 20 ms 24276 KB n=2000
88 Correct 15 ms 24340 KB n=2000
89 Correct 15 ms 24328 KB n=2000
90 Correct 15 ms 24344 KB n=2000
91 Correct 15 ms 24276 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 11 ms 23800 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 18 ms 23824 KB n=100
6 Correct 15 ms 23824 KB n=100
7 Correct 13 ms 23852 KB n=100
8 Correct 18 ms 23816 KB n=100
9 Correct 13 ms 23820 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 15 ms 23796 KB n=100
13 Correct 15 ms 23820 KB n=100
14 Correct 13 ms 23764 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 14 ms 23844 KB n=100
17 Correct 13 ms 23776 KB n=100
18 Correct 13 ms 23764 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 13 ms 23768 KB n=100
21 Correct 12 ms 23764 KB n=100
22 Correct 16 ms 23836 KB n=100
23 Correct 13 ms 23764 KB n=100
24 Correct 16 ms 23764 KB n=100
25 Correct 15 ms 23792 KB n=100
26 Correct 18 ms 23816 KB n=12
27 Correct 16 ms 23820 KB n=100
28 Correct 14 ms 23880 KB n=500
29 Correct 17 ms 23892 KB n=500
30 Correct 14 ms 23960 KB n=500
31 Correct 17 ms 23892 KB n=500
32 Correct 17 ms 23920 KB n=500
33 Correct 14 ms 23900 KB n=500
34 Correct 17 ms 23960 KB n=500
35 Correct 16 ms 23960 KB n=500
36 Correct 14 ms 23848 KB n=500
37 Correct 13 ms 23948 KB n=500
38 Correct 13 ms 23960 KB n=500
39 Correct 14 ms 23892 KB n=500
40 Correct 17 ms 23852 KB n=500
41 Correct 18 ms 23964 KB n=500
42 Correct 17 ms 23892 KB n=500
43 Correct 14 ms 23892 KB n=500
44 Correct 14 ms 23856 KB n=500
45 Correct 15 ms 23892 KB n=500
46 Correct 14 ms 23960 KB n=500
47 Correct 14 ms 23892 KB n=500
48 Correct 14 ms 23892 KB n=500
49 Correct 17 ms 23892 KB n=500
50 Correct 17 ms 23948 KB n=500
51 Correct 16 ms 23952 KB n=500
52 Correct 17 ms 23896 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 17 ms 23864 KB n=500
55 Correct 15 ms 23892 KB n=278
56 Correct 16 ms 23872 KB n=500
57 Correct 13 ms 23892 KB n=500
58 Correct 18 ms 23920 KB n=500
59 Correct 16 ms 24276 KB n=2000
60 Correct 16 ms 24344 KB n=2000
61 Correct 16 ms 24276 KB n=2000
62 Correct 21 ms 24320 KB n=2000
63 Correct 16 ms 24264 KB n=2000
64 Correct 16 ms 24296 KB n=2000
65 Correct 16 ms 24216 KB n=2000
66 Correct 16 ms 24276 KB n=2000
67 Correct 18 ms 24200 KB n=2000
68 Correct 16 ms 24276 KB n=2000
69 Correct 15 ms 24276 KB n=2000
70 Correct 15 ms 24276 KB n=2000
71 Correct 15 ms 24276 KB n=2000
72 Correct 15 ms 24216 KB n=2000
73 Correct 15 ms 24252 KB n=2000
74 Correct 16 ms 24240 KB n=1844
75 Correct 16 ms 24216 KB n=2000
76 Correct 20 ms 24252 KB n=2000
77 Correct 18 ms 24276 KB n=2000
78 Correct 17 ms 24292 KB n=2000
79 Correct 17 ms 24276 KB n=2000
80 Correct 18 ms 24348 KB n=2000
81 Correct 16 ms 24272 KB n=2000
82 Correct 21 ms 24204 KB n=2000
83 Correct 19 ms 24348 KB n=2000
84 Correct 16 ms 24276 KB n=2000
85 Correct 16 ms 24244 KB n=2000
86 Correct 16 ms 24276 KB n=2000
87 Correct 20 ms 24276 KB n=2000
88 Correct 15 ms 24340 KB n=2000
89 Correct 15 ms 24328 KB n=2000
90 Correct 15 ms 24344 KB n=2000
91 Correct 15 ms 24276 KB n=2000
92 Correct 678 ms 74456 KB n=200000
93 Correct 906 ms 79332 KB n=200000
94 Correct 857 ms 82796 KB n=200000
95 Correct 616 ms 74328 KB n=200000
96 Correct 619 ms 74336 KB n=200000
97 Correct 885 ms 78656 KB n=200000
98 Correct 657 ms 74444 KB n=200000
99 Correct 731 ms 74416 KB n=200000
100 Correct 595 ms 74320 KB n=200000
101 Correct 787 ms 84040 KB n=200000
102 Correct 374 ms 75572 KB n=200000
103 Correct 383 ms 75464 KB n=200000
104 Correct 387 ms 75468 KB n=200000
105 Correct 365 ms 75980 KB n=200000
106 Correct 388 ms 75976 KB n=200000
107 Correct 378 ms 75960 KB n=200000
108 Correct 683 ms 74560 KB n=200000
109 Correct 664 ms 74564 KB n=200000
110 Correct 662 ms 74464 KB n=200000
111 Correct 593 ms 73864 KB n=200000
112 Correct 764 ms 83020 KB n=200000
113 Correct 792 ms 78428 KB n=200000
114 Correct 571 ms 74012 KB n=200000
115 Correct 859 ms 76376 KB n=200000
116 Correct 589 ms 74544 KB n=200000
117 Correct 835 ms 83492 KB n=200000
118 Correct 991 ms 77280 KB n=200000
119 Correct 580 ms 74620 KB n=200000
120 Correct 890 ms 82988 KB n=200000
121 Correct 769 ms 83076 KB n=200000
122 Correct 772 ms 83308 KB n=200000
123 Correct 399 ms 75724 KB n=200000
124 Correct 173 ms 38696 KB n=25264