oj.uz

Submission #1100605

# Submission time Handle Problem Language Result Execution time Memory
1100605 2024-10-14T10:20:55 Z vjudge1 Birthday gift (IZhO18_treearray) C++
30 / 100
 4000 ms 9024 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 200005, M = 20;
int up[N][M], dep[N], tin[N], tout[N], timer = 0;
int a[N];
vector<int> adj[N];
//dfs
void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for(int i = 1; i < M; i++)
    {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int u : adj[v]) 
    {
        if(u != p)
        {
            dep[u] = dep[v] + 1;
            dfs(u, v);
        }
    }
    tout[v] = ++timer;
}
// предок па?
bool is(int v, int u)
{
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}
//наименьший общий предок иуу
int lca(int u, int v)
{
    if(is(u, v))
    {
        return u;
    }
    if(is(v, u))
    {
        return v;
    }
    for(int i = M - 1; i >= 0; i--)
    {
        if(!is(up[u][i], v)) 
        {
            u = up[u][i];
        }
    }
    return up[u][0];
}
int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1);
    for(int i = 0; i < m; i++)
    {
        cin >> a[i];
    }
    for(int i = 0; i < q; i++)
    {
        int tp;
        cin >> tp;
        //запрашиваем типы
        if(tp == 1)
        {
            int pos, v;
            cin >> pos >> v;
            pos--;
            a[pos] = v;
        }
        else if(tp == 2) 
        {
            int l, r, v;
            cin >> l >> r >> v;
            l--;
            r--;
            bool ok = false;
            for(int x = l; x <= r && !ok; x++)
            {
                int cur = a[x];
                for(int y = x; y <= r; y++)
                {
                    cur = lca(cur, a[y]);
                    if(cur == v)
                    {
                        cout << x + 1 << " " << y + 1 << endl;
                        ok = true;
                        break;
                    }
                }
            }
            if(!ok)
            {
                cout << -1 << " " << -1 << endl;
            }
        }
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB n=5
2 Correct 2 ms 8784 KB n=100
3 Correct 2 ms 8784 KB n=100
4 Correct 2 ms 8784 KB n=100
5 Correct 2 ms 8956 KB n=100
6 Correct 3 ms 8784 KB n=100
7 Correct 3 ms 8784 KB n=100
8 Correct 2 ms 8784 KB n=100
9 Correct 2 ms 8784 KB n=100
10 Correct 3 ms 8952 KB n=100
11 Correct 2 ms 8784 KB n=100
12 Correct 3 ms 8952 KB n=100
13 Correct 2 ms 8784 KB n=100
14 Correct 2 ms 8784 KB n=100
15 Correct 2 ms 8784 KB n=100
16 Correct 2 ms 8784 KB n=100
17 Correct 2 ms 8784 KB n=100
18 Correct 2 ms 8784 KB n=100
19 Correct 2 ms 8784 KB n=100
20 Correct 2 ms 8784 KB n=100
21 Correct 2 ms 8784 KB n=100
22 Correct 2 ms 8952 KB n=100
23 Correct 2 ms 8784 KB n=100
24 Correct 2 ms 8784 KB n=100
25 Correct 3 ms 8796 KB n=100
26 Correct 2 ms 8952 KB n=12
27 Correct 3 ms 8784 KB n=100
28 Correct 3 ms 8784 KB n=500
29 Correct 12 ms 8784 KB n=500
30 Correct 11 ms 8784 KB n=500
31 Correct 12 ms 8796 KB n=500
32 Correct 3 ms 8796 KB n=500
33 Correct 10 ms 8784 KB n=500
34 Correct 3 ms 8784 KB n=500
35 Correct 12 ms 8784 KB n=500
36 Correct 107 ms 8784 KB n=500
37 Correct 111 ms 8784 KB n=500
38 Correct 107 ms 8952 KB n=500
39 Correct 20 ms 8784 KB n=500
40 Correct 19 ms 8784 KB n=500
41 Correct 19 ms 8784 KB n=500
42 Correct 55 ms 8784 KB n=500
43 Correct 60 ms 8784 KB n=500
44 Correct 62 ms 8784 KB n=500
45 Correct 3 ms 8800 KB n=500
46 Correct 11 ms 8952 KB n=500
47 Correct 10 ms 8796 KB n=500
48 Correct 3 ms 8796 KB n=500
49 Correct 10 ms 8800 KB n=500
50 Correct 16 ms 8796 KB n=500
51 Correct 17 ms 8800 KB n=500
52 Correct 19 ms 8796 KB n=500
53 Correct 19 ms 8952 KB n=500
54 Correct 9 ms 8796 KB n=500
55 Correct 4 ms 8952 KB n=278
56 Correct 56 ms 8952 KB n=500
57 Correct 58 ms 8796 KB n=500
58 Correct 53 ms 8800 KB n=500
59 Correct 12 ms 8796 KB n=2000
60 Correct 525 ms 9024 KB n=2000
61 Correct 576 ms 8796 KB n=2000
62 Correct 358 ms 8784 KB n=2000
63 Correct 16 ms 8784 KB n=2000
64 Correct 511 ms 8784 KB n=2000
65 Correct 6 ms 8784 KB n=2000
66 Correct 583 ms 8784 KB n=2000
67 Correct 31 ms 8900 KB n=2000
68 Correct 475 ms 8956 KB n=2000
69 Execution timed out 4074 ms 8884 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB n=5
2 Correct 2 ms 8784 KB n=100
3 Correct 2 ms 8784 KB n=100
4 Correct 2 ms 8784 KB n=100
5 Correct 2 ms 8956 KB n=100
6 Correct 3 ms 8784 KB n=100
7 Correct 3 ms 8784 KB n=100
8 Correct 2 ms 8784 KB n=100
9 Correct 2 ms 8784 KB n=100
10 Correct 3 ms 8952 KB n=100
11 Correct 2 ms 8784 KB n=100
12 Correct 3 ms 8952 KB n=100
13 Correct 2 ms 8784 KB n=100
14 Correct 2 ms 8784 KB n=100
15 Correct 2 ms 8784 KB n=100
16 Correct 2 ms 8784 KB n=100
17 Correct 2 ms 8784 KB n=100
18 Correct 2 ms 8784 KB n=100
19 Correct 2 ms 8784 KB n=100
20 Correct 2 ms 8784 KB n=100
21 Correct 2 ms 8784 KB n=100
22 Correct 2 ms 8952 KB n=100
23 Correct 2 ms 8784 KB n=100
24 Correct 2 ms 8784 KB n=100
25 Correct 3 ms 8796 KB n=100
26 Correct 2 ms 8952 KB n=12
27 Correct 3 ms 8784 KB n=100
28 Correct 3 ms 8784 KB n=500
29 Correct 12 ms 8784 KB n=500
30 Correct 11 ms 8784 KB n=500
31 Correct 12 ms 8796 KB n=500
32 Correct 3 ms 8796 KB n=500
33 Correct 10 ms 8784 KB n=500
34 Correct 3 ms 8784 KB n=500
35 Correct 12 ms 8784 KB n=500
36 Correct 107 ms 8784 KB n=500
37 Correct 111 ms 8784 KB n=500
38 Correct 107 ms 8952 KB n=500
39 Correct 20 ms 8784 KB n=500
40 Correct 19 ms 8784 KB n=500
41 Correct 19 ms 8784 KB n=500
42 Correct 55 ms 8784 KB n=500
43 Correct 60 ms 8784 KB n=500
44 Correct 62 ms 8784 KB n=500
45 Correct 3 ms 8800 KB n=500
46 Correct 11 ms 8952 KB n=500
47 Correct 10 ms 8796 KB n=500
48 Correct 3 ms 8796 KB n=500
49 Correct 10 ms 8800 KB n=500
50 Correct 16 ms 8796 KB n=500
51 Correct 17 ms 8800 KB n=500
52 Correct 19 ms 8796 KB n=500
53 Correct 19 ms 8952 KB n=500
54 Correct 9 ms 8796 KB n=500
55 Correct 4 ms 8952 KB n=278
56 Correct 56 ms 8952 KB n=500
57 Correct 58 ms 8796 KB n=500
58 Correct 53 ms 8800 KB n=500
59 Correct 12 ms 8796 KB n=2000
60 Correct 525 ms 9024 KB n=2000
61 Correct 576 ms 8796 KB n=2000
62 Correct 358 ms 8784 KB n=2000
63 Correct 16 ms 8784 KB n=2000
64 Correct 511 ms 8784 KB n=2000
65 Correct 6 ms 8784 KB n=2000
66 Correct 583 ms 8784 KB n=2000
67 Correct 31 ms 8900 KB n=2000
68 Correct 475 ms 8956 KB n=2000
69 Execution timed out 4074 ms 8884 KB Time limit exceeded
70 Halted 0 ms 0 KB -