oj.uz

Submission #527323

# Submission time Handle Problem Language Result Execution time Memory
527323 2022-02-17T07:31:38 Z jalsol Birthday gift (IZhO18_treearray) C++11
56 / 100
 4000 ms 40924 KB 
#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxN = 2e5 + 5;
constexpr int logN = 20;

int n, m, nq;
vector<int> g[maxN];
int a[maxN];

int par[maxN][logN];
int dep[maxN];

int tree[maxN << 2];

void Dfs(int u) {
    for (int v : g[u]) if (v != par[u][0]) {
        par[v][0] = u;
        dep[v] = dep[u] + 1;
        Dfs(v);
    }
}

int getLca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);

    Repd (i, logN) if ((dep[u] - dep[v]) >> i & 1) {
        u = par[u][i];
    }

    if (u == v) return u;

    Repd (i, logN) if (par[u][i] != par[v][i]) {
        u = par[u][i];
        v = par[v][i];
    }

    return par[u][0];
}

#define m ((l + r) >> 1)
#define tl (i << 1)
#define tr (i << 1 | 1)

void build(int i, int l, int r) {
    if (l == r) {
        tree[i] = a[l];
        return;
    }

    build(tl, l, m);
    build(tr, m + 1, r);
    tree[i] = getLca(tree[tl], tree[tr]);
}

void update(int p, int x, int i, int l, int r) {
    if (p < l || r < p) return;

    if (l == r) {
        tree[i] = x;
        return;
    }

    update(p, x, tl, l, m);
    update(p, x, tr, m + 1, r);
    tree[i] = getLca(tree[tl], tree[tr]);
}

int get(int u, int v, int i, int l, int r) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return tree[i];

    int left = get(u, v, tl, l, m);
    int right = get(u, v, tr, m + 1, r);

    if (!left) left = right;
    if (!right) right = left;
    return getLca(left, right);
}

#undef m
#undef tl
#undef tr

signed main() {
    cin >> n >> m >> nq;

    Rep (_, n - 1) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    For (i, 1, m) cin >> a[i];

    Dfs(1);

    For (j, 1, logN - 1) {
        For (i, 1, n) {
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }

    build(1, 1, m);

    Rep (_, nq) {
        int op; cin >> op;

        if (op == 1) {
            int p, x; cin >> p >> x;
            update(p, x, 1, 1, m);
        } else {
            int l, r, v; cin >> l >> r >> v;
            int ansL = -1, ansR = -1;
            int pL = l, pR = l;

            while (pL <= r && pR <= r) {
                if (pL > pR) pR = pL;

                int lca = get(pL, pR, 1, 1, m);
                if (lca == v) {
                    ansL = pL;
                    ansR = pR;
                    break;
                }

                if (dep[lca] < dep[v]) {
                    ++pL;
                } else {
                    ++pR;
                }
            }


            cout << ansL << ' ' << ansR << '\n';
        }
    }
}

/*

*/

Compilation message

treearray.cpp: In constructor '__Init__::__Init__()':
treearray.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB n=5
2 Correct 3 ms 4940 KB n=100
3 Correct 4 ms 5048 KB n=100
4 Correct 3 ms 4940 KB n=100
5 Correct 3 ms 4940 KB n=100
6 Correct 6 ms 4940 KB n=100
7 Correct 5 ms 4940 KB n=100
8 Correct 4 ms 4940 KB n=100
9 Correct 4 ms 4940 KB n=100
10 Correct 4 ms 4940 KB n=100
11 Correct 5 ms 4940 KB n=100
12 Correct 5 ms 4940 KB n=100
13 Correct 3 ms 4940 KB n=100
14 Correct 3 ms 4940 KB n=100
15 Correct 3 ms 4940 KB n=100
16 Correct 3 ms 4940 KB n=100
17 Correct 3 ms 4940 KB n=100
18 Correct 3 ms 4940 KB n=100
19 Correct 3 ms 4940 KB n=100
20 Correct 3 ms 4940 KB n=100
21 Correct 4 ms 4944 KB n=100
22 Correct 2 ms 4940 KB n=100
23 Correct 5 ms 4940 KB n=100
24 Correct 6 ms 4940 KB n=100
25 Correct 3 ms 4940 KB n=100
26 Correct 3 ms 4940 KB n=12
27 Correct 5 ms 4992 KB n=100
28 Correct 3 ms 5068 KB n=500
29 Correct 16 ms 5124 KB n=500
30 Correct 15 ms 5112 KB n=500
31 Correct 16 ms 5120 KB n=500
32 Correct 3 ms 5068 KB n=500
33 Correct 13 ms 5068 KB n=500
34 Correct 3 ms 5068 KB n=500
35 Correct 15 ms 5128 KB n=500
36 Correct 82 ms 5080 KB n=500
37 Correct 84 ms 5080 KB n=500
38 Correct 77 ms 5084 KB n=500
39 Correct 41 ms 5096 KB n=500
40 Correct 42 ms 5096 KB n=500
41 Correct 40 ms 5096 KB n=500
42 Correct 42 ms 5084 KB n=500
43 Correct 42 ms 5100 KB n=500
44 Correct 40 ms 5100 KB n=500
45 Correct 3 ms 5068 KB n=500
46 Correct 18 ms 5128 KB n=500
47 Correct 15 ms 5120 KB n=500
48 Correct 3 ms 5068 KB n=500
49 Correct 12 ms 5128 KB n=500
50 Correct 23 ms 5068 KB n=500
51 Correct 19 ms 5112 KB n=500
52 Correct 28 ms 5128 KB n=500
53 Correct 21 ms 5112 KB n=500
54 Correct 31 ms 5108 KB n=500
55 Correct 5 ms 5068 KB n=278
56 Correct 64 ms 5128 KB n=500
57 Correct 64 ms 5112 KB n=500
58 Correct 50 ms 5104 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB n=5
2 Correct 3 ms 4940 KB n=100
3 Correct 4 ms 5048 KB n=100
4 Correct 3 ms 4940 KB n=100
5 Correct 3 ms 4940 KB n=100
6 Correct 6 ms 4940 KB n=100
7 Correct 5 ms 4940 KB n=100
8 Correct 4 ms 4940 KB n=100
9 Correct 4 ms 4940 KB n=100
10 Correct 4 ms 4940 KB n=100
11 Correct 5 ms 4940 KB n=100
12 Correct 5 ms 4940 KB n=100
13 Correct 3 ms 4940 KB n=100
14 Correct 3 ms 4940 KB n=100
15 Correct 3 ms 4940 KB n=100
16 Correct 3 ms 4940 KB n=100
17 Correct 3 ms 4940 KB n=100
18 Correct 3 ms 4940 KB n=100
19 Correct 3 ms 4940 KB n=100
20 Correct 3 ms 4940 KB n=100
21 Correct 4 ms 4944 KB n=100
22 Correct 2 ms 4940 KB n=100
23 Correct 5 ms 4940 KB n=100
24 Correct 6 ms 4940 KB n=100
25 Correct 3 ms 4940 KB n=100
26 Correct 3 ms 4940 KB n=12
27 Correct 5 ms 4992 KB n=100
28 Correct 3 ms 5068 KB n=500
29 Correct 16 ms 5124 KB n=500
30 Correct 15 ms 5112 KB n=500
31 Correct 16 ms 5120 KB n=500
32 Correct 3 ms 5068 KB n=500
33 Correct 13 ms 5068 KB n=500
34 Correct 3 ms 5068 KB n=500
35 Correct 15 ms 5128 KB n=500
36 Correct 82 ms 5080 KB n=500
37 Correct 84 ms 5080 KB n=500
38 Correct 77 ms 5084 KB n=500
39 Correct 41 ms 5096 KB n=500
40 Correct 42 ms 5096 KB n=500
41 Correct 40 ms 5096 KB n=500
42 Correct 42 ms 5084 KB n=500
43 Correct 42 ms 5100 KB n=500
44 Correct 40 ms 5100 KB n=500
45 Correct 3 ms 5068 KB n=500
46 Correct 18 ms 5128 KB n=500
47 Correct 15 ms 5120 KB n=500
48 Correct 3 ms 5068 KB n=500
49 Correct 12 ms 5128 KB n=500
50 Correct 23 ms 5068 KB n=500
51 Correct 19 ms 5112 KB n=500
52 Correct 28 ms 5128 KB n=500
53 Correct 21 ms 5112 KB n=500
54 Correct 31 ms 5108 KB n=500
55 Correct 5 ms 5068 KB n=278
56 Correct 64 ms 5128 KB n=500
57 Correct 64 ms 5112 KB n=500
58 Correct 50 ms 5104 KB n=500
59 Correct 7 ms 5196 KB n=2000
60 Correct 263 ms 5396 KB n=2000
61 Correct 247 ms 5340 KB n=2000
62 Correct 180 ms 5316 KB n=2000
63 Correct 8 ms 5312 KB n=2000
64 Correct 206 ms 5336 KB n=2000
65 Correct 7 ms 5300 KB n=2000
66 Correct 262 ms 5360 KB n=2000
67 Correct 16 ms 5196 KB n=2000
68 Correct 226 ms 5324 KB n=2000
69 Correct 1431 ms 5408 KB n=2000
70 Correct 1492 ms 5588 KB n=2000
71 Correct 1510 ms 5336 KB n=2000
72 Correct 806 ms 5328 KB n=2000
73 Correct 746 ms 5328 KB n=2000
74 Correct 5 ms 5188 KB n=1844
75 Correct 762 ms 5328 KB n=2000
76 Correct 784 ms 5324 KB n=2000
77 Correct 769 ms 5328 KB n=2000
78 Correct 815 ms 5336 KB n=2000
79 Correct 5 ms 5324 KB n=2000
80 Correct 245 ms 5432 KB n=2000
81 Correct 198 ms 5380 KB n=2000
82 Correct 5 ms 5324 KB n=2000
83 Correct 206 ms 5416 KB n=2000
84 Correct 374 ms 5336 KB n=2000
85 Correct 316 ms 5324 KB n=2000
86 Correct 318 ms 5368 KB n=2000
87 Correct 366 ms 5340 KB n=2000
88 Correct 1452 ms 5452 KB n=2000
89 Correct 1508 ms 5452 KB n=2000
90 Correct 412 ms 5452 KB n=2000
91 Correct 1073 ms 5340 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB n=5
2 Correct 3 ms 4940 KB n=100
3 Correct 4 ms 5048 KB n=100
4 Correct 3 ms 4940 KB n=100
5 Correct 3 ms 4940 KB n=100
6 Correct 6 ms 4940 KB n=100
7 Correct 5 ms 4940 KB n=100
8 Correct 4 ms 4940 KB n=100
9 Correct 4 ms 4940 KB n=100
10 Correct 4 ms 4940 KB n=100
11 Correct 5 ms 4940 KB n=100
12 Correct 5 ms 4940 KB n=100
13 Correct 3 ms 4940 KB n=100
14 Correct 3 ms 4940 KB n=100
15 Correct 3 ms 4940 KB n=100
16 Correct 3 ms 4940 KB n=100
17 Correct 3 ms 4940 KB n=100
18 Correct 3 ms 4940 KB n=100
19 Correct 3 ms 4940 KB n=100
20 Correct 3 ms 4940 KB n=100
21 Correct 4 ms 4944 KB n=100
22 Correct 2 ms 4940 KB n=100
23 Correct 5 ms 4940 KB n=100
24 Correct 6 ms 4940 KB n=100
25 Correct 3 ms 4940 KB n=100
26 Correct 3 ms 4940 KB n=12
27 Correct 5 ms 4992 KB n=100
28 Correct 3 ms 5068 KB n=500
29 Correct 16 ms 5124 KB n=500
30 Correct 15 ms 5112 KB n=500
31 Correct 16 ms 5120 KB n=500
32 Correct 3 ms 5068 KB n=500
33 Correct 13 ms 5068 KB n=500
34 Correct 3 ms 5068 KB n=500
35 Correct 15 ms 5128 KB n=500
36 Correct 82 ms 5080 KB n=500
37 Correct 84 ms 5080 KB n=500
38 Correct 77 ms 5084 KB n=500
39 Correct 41 ms 5096 KB n=500
40 Correct 42 ms 5096 KB n=500
41 Correct 40 ms 5096 KB n=500
42 Correct 42 ms 5084 KB n=500
43 Correct 42 ms 5100 KB n=500
44 Correct 40 ms 5100 KB n=500
45 Correct 3 ms 5068 KB n=500
46 Correct 18 ms 5128 KB n=500
47 Correct 15 ms 5120 KB n=500
48 Correct 3 ms 5068 KB n=500
49 Correct 12 ms 5128 KB n=500
50 Correct 23 ms 5068 KB n=500
51 Correct 19 ms 5112 KB n=500
52 Correct 28 ms 5128 KB n=500
53 Correct 21 ms 5112 KB n=500
54 Correct 31 ms 5108 KB n=500
55 Correct 5 ms 5068 KB n=278
56 Correct 64 ms 5128 KB n=500
57 Correct 64 ms 5112 KB n=500
58 Correct 50 ms 5104 KB n=500
59 Correct 7 ms 5196 KB n=2000
60 Correct 263 ms 5396 KB n=2000
61 Correct 247 ms 5340 KB n=2000
62 Correct 180 ms 5316 KB n=2000
63 Correct 8 ms 5312 KB n=2000
64 Correct 206 ms 5336 KB n=2000
65 Correct 7 ms 5300 KB n=2000
66 Correct 262 ms 5360 KB n=2000
67 Correct 16 ms 5196 KB n=2000
68 Correct 226 ms 5324 KB n=2000
69 Correct 1431 ms 5408 KB n=2000
70 Correct 1492 ms 5588 KB n=2000
71 Correct 1510 ms 5336 KB n=2000
72 Correct 806 ms 5328 KB n=2000
73 Correct 746 ms 5328 KB n=2000
74 Correct 5 ms 5188 KB n=1844
75 Correct 762 ms 5328 KB n=2000
76 Correct 784 ms 5324 KB n=2000
77 Correct 769 ms 5328 KB n=2000
78 Correct 815 ms 5336 KB n=2000
79 Correct 5 ms 5324 KB n=2000
80 Correct 245 ms 5432 KB n=2000
81 Correct 198 ms 5380 KB n=2000
82 Correct 5 ms 5324 KB n=2000
83 Correct 206 ms 5416 KB n=2000
84 Correct 374 ms 5336 KB n=2000
85 Correct 316 ms 5324 KB n=2000
86 Correct 318 ms 5368 KB n=2000
87 Correct 366 ms 5340 KB n=2000
88 Correct 1452 ms 5452 KB n=2000
89 Correct 1508 ms 5452 KB n=2000
90 Correct 412 ms 5452 KB n=2000
91 Correct 1073 ms 5340 KB n=2000
92 Correct 3515 ms 38960 KB n=200000
93 Execution timed out 4038 ms 40924 KB Time limit exceeded
94 Halted 0 ms 0 KB -