oj.uz

Submission #257452

# Submission time Handle Problem Language Result Execution time Memory
257452 2020-08-04T09:35:42 Z karma Birthday gift (IZhO18_treearray) C++14
100 / 100
 1301 ms 83320 KB 
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = int(2e5) + 7;
const int logN = 18;
typedef pair<int, int> pii;

int n, m, q, a[N];
int p[N][logN + 1], d[N];
vector<int> adj[N];

void dfs(int u) {
    for(int i = 1; i <= logN; ++i) p[u][i] = p[p[u][i - 1]][i - 1];
    for(int v: adj[u]) {
        if(v == p[u][0]) continue;
        p[v][0] = u;
        d[v] = d[u] + 1;
        dfs(v);
    }
}

int lca(int u, int v) {
    if(d[u] < d[v]) swap(u, v);
    for(int i = logN; i >= 0; --i)
        if(d[u] - (1 << i) >= d[v]) u = p[u][i];
    if(u == v) return u;
    for(int i = logN; i >= 0; --i)
        if(p[u][i] != p[v][i])
            u = p[u][i], v = p[v][i];
    return p[u][0];
}

set<int> s[2][N];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> m >> q;
    for(int u, v, i = 1; i < n; ++i) {
        cin >> u >> v;
        adj[u].pb(v), adj[v].pb(u);
    }
    dfs(1);
    for(int i = 1; i <= m; ++i) {
        cin >> a[i];
        s[0][a[i]].insert(i);
        if(i > 1) s[1][lca(a[i], a[i - 1])].insert(i - 1);
    }
    int cmd, l, r, u;
    while(q --) {
        cin >> cmd;
        if(cmd == 1) {
            cin >> l >> u;
            s[0][a[l]].erase(l);
            if(l < m) s[1][lca(a[l], a[l + 1])].erase(l);
            if(l > 1) s[1][lca(a[l], a[l - 1])].erase(l - 1);
            a[l] = u;
            s[0][a[l]].insert(l);
            if(l < m) s[1][lca(a[l], a[l + 1])].insert(l);
            if(l > 1) s[1][lca(a[l], a[l - 1])].insert(l - 1);
        } else {
            cin >> l >> r >> u;
            auto it0 = s[0][u].lower_bound(l);
            if(it0 != s[0][u].end() && *it0 <= r) {
                cout << *it0 << ' ' << *it0 << '\n';
                continue;
            }
            auto it1 = s[1][u].lower_bound(l);
            if(it1 != s[1][u].end() && *it1 + 1 <= r) {
                cout << *it1 << ' '  << *it1 + 1 << '\n';
                continue;
            }
            cout << "-1 -1\n";
        }
    }
}

Compilation message

treearray.cpp: In function 'int32_t main()':
treearray.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB n=5
2 Correct 15 ms 23808 KB n=100
3 Correct 14 ms 23808 KB n=100
4 Correct 14 ms 23808 KB n=100
5 Correct 13 ms 23808 KB n=100
6 Correct 14 ms 23808 KB n=100
7 Correct 13 ms 23808 KB n=100
8 Correct 14 ms 23808 KB n=100
9 Correct 13 ms 23808 KB n=100
10 Correct 20 ms 23808 KB n=100
11 Correct 16 ms 23808 KB n=100
12 Correct 15 ms 23808 KB n=100
13 Correct 19 ms 23808 KB n=100
14 Correct 13 ms 23808 KB n=100
15 Correct 14 ms 23808 KB n=100
16 Correct 13 ms 23808 KB n=100
17 Correct 14 ms 23912 KB n=100
18 Correct 14 ms 23808 KB n=100
19 Correct 13 ms 23808 KB n=100
20 Correct 14 ms 23808 KB n=100
21 Correct 14 ms 23808 KB n=100
22 Correct 14 ms 23808 KB n=100
23 Correct 14 ms 23808 KB n=100
24 Correct 15 ms 23808 KB n=100
25 Correct 14 ms 23808 KB n=100
26 Correct 14 ms 23808 KB n=12
27 Correct 15 ms 23808 KB n=100
28 Correct 14 ms 23936 KB n=500
29 Correct 15 ms 23936 KB n=500
30 Correct 18 ms 23936 KB n=500
31 Correct 17 ms 23936 KB n=500
32 Correct 17 ms 23936 KB n=500
33 Correct 14 ms 23916 KB n=500
34 Correct 14 ms 23936 KB n=500
35 Correct 14 ms 23936 KB n=500
36 Correct 17 ms 23936 KB n=500
37 Correct 15 ms 23936 KB n=500
38 Correct 14 ms 23936 KB n=500
39 Correct 15 ms 23936 KB n=500
40 Correct 15 ms 24064 KB n=500
41 Correct 17 ms 23936 KB n=500
42 Correct 14 ms 23936 KB n=500
43 Correct 16 ms 23888 KB n=500
44 Correct 14 ms 23936 KB n=500
45 Correct 14 ms 23936 KB n=500
46 Correct 16 ms 24084 KB n=500
47 Correct 15 ms 23936 KB n=500
48 Correct 15 ms 23936 KB n=500
49 Correct 16 ms 24040 KB n=500
50 Correct 15 ms 24124 KB n=500
51 Correct 15 ms 23936 KB n=500
52 Correct 14 ms 23936 KB n=500
53 Correct 15 ms 23936 KB n=500
54 Correct 15 ms 23936 KB n=500
55 Correct 15 ms 23936 KB n=278
56 Correct 14 ms 23936 KB n=500
57 Correct 14 ms 23936 KB n=500
58 Correct 14 ms 23936 KB n=500
59 Correct 19 ms 24320 KB n=2000
60 Correct 17 ms 24448 KB n=2000
61 Correct 18 ms 24320 KB n=2000
62 Correct 18 ms 24320 KB n=2000
63 Correct 20 ms 24320 KB n=2000
64 Correct 19 ms 24320 KB n=2000
65 Correct 18 ms 24320 KB n=2000
66 Correct 18 ms 24380 KB n=2000
67 Correct 21 ms 24316 KB n=2000
68 Correct 18 ms 24312 KB n=2000
69 Correct 18 ms 24320 KB n=2000
70 Correct 20 ms 24316 KB n=2000
71 Correct 17 ms 24320 KB n=2000
72 Correct 18 ms 24320 KB n=2000
73 Correct 19 ms 24448 KB n=2000
74 Correct 16 ms 24320 KB n=1844
75 Correct 23 ms 24312 KB n=2000
76 Correct 21 ms 24320 KB n=2000
77 Correct 21 ms 24296 KB n=2000
78 Correct 19 ms 24320 KB n=2000
79 Correct 18 ms 24320 KB n=2000
80 Correct 23 ms 24372 KB n=2000
81 Correct 24 ms 24412 KB n=2000
82 Correct 18 ms 24320 KB n=2000
83 Correct 19 ms 24448 KB n=2000
84 Correct 17 ms 24320 KB n=2000
85 Correct 17 ms 24320 KB n=2000
86 Correct 17 ms 24392 KB n=2000
87 Correct 21 ms 24320 KB n=2000
88 Correct 17 ms 24448 KB n=2000
89 Correct 18 ms 24448 KB n=2000
90 Correct 17 ms 24448 KB n=2000
91 Correct 22 ms 24320 KB n=2000
92 Correct 931 ms 73788 KB n=200000
93 Correct 1176 ms 79052 KB n=200000
94 Correct 1130 ms 82168 KB n=200000
95 Correct 825 ms 73576 KB n=200000
96 Correct 814 ms 73704 KB n=200000
97 Correct 1189 ms 78056 KB n=200000
98 Correct 806 ms 73712 KB n=200000
99 Correct 1008 ms 73980 KB n=200000
100 Correct 819 ms 73944 KB n=200000
101 Correct 1120 ms 83320 KB n=200000
102 Correct 518 ms 74872 KB n=200000
103 Correct 498 ms 75000 KB n=200000
104 Correct 490 ms 74964 KB n=200000
105 Correct 509 ms 75260 KB n=200000
106 Correct 511 ms 75512 KB n=200000
107 Correct 512 ms 75396 KB n=200000
108 Correct 1014 ms 73720 KB n=200000
109 Correct 943 ms 73884 KB n=200000
110 Correct 940 ms 73980 KB n=200000
111 Correct 849 ms 73072 KB n=200000
112 Correct 1176 ms 82564 KB n=200000
113 Correct 1227 ms 77972 KB n=200000
114 Correct 946 ms 73324 KB n=200000
115 Correct 1301 ms 75896 KB n=200000
116 Correct 800 ms 74088 KB n=200000
117 Correct 1132 ms 82808 KB n=200000
118 Correct 1293 ms 76792 KB n=200000
119 Correct 778 ms 74088 KB n=200000
120 Correct 1081 ms 82352 KB n=200000
121 Correct 1083 ms 82296 KB n=200000
122 Correct 1107 ms 82708 KB n=200000
123 Correct 563 ms 75128 KB n=200000
124 Correct 257 ms 38648 KB n=25264