oj.uz

Submission #1007741

# Submission time Handle Problem Language Result Execution time Memory
1007741 2024-06-25T12:18:36 Z ByeWorld Birthday gift (IZhO18_treearray) C++14
56 / 100
 4000 ms 57484 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 2e5+10;
const int MAXA = 2e3+10;
const int INF = 1e18+10;
const int LOG = 19;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};

int n, m, q;
int a[MAXN];
vector <int> adj[MAXN];
bool b[MAXN];
int anc[MAXN][LOG+5], dep[MAXN];

void dfs(int nw, int par){
    anc[nw][0] = par; dep[nw] = dep[par]+1;
    for(auto nx : adj[nw]){
        if(nx==par) continue;
        dfs(nx, nw);
    }
}
int LCA(int x, int y){
    if(dep[x] > dep[y]) swap(x, y);
    for(int i=LOG-1; i>=0; i--){
        if(dep[anc[y][i]] >= dep[x])
            y = anc[y][i];
    }
    if(x==y) return x;
    for(int i=LOG-1; i>=0; i--){
        if(anc[x][i] != anc[y][i]){
            x = anc[x][i]; y = anc[y][i];
        }
    }
    return anc[x][0];
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i=1; i<=n-1; i++){
        int x, y; cin >> x >> y;
        adj[x].pb(y); adj[y].pb(x);
    }
    dfs(1, 0);
    for(int j=1; j<LOG; j++)
        for(int i=1; i<=n; i++)
            anc[i][j] = anc[anc[i][j-1]][j-1];

    for(int i=1; i<=m; i++) cin >> a[i];
    for(int xx=1; xx<=q; xx++){
        int ty; cin >> ty;
        if(ty==1){
            int pos, x; cin >> pos >> x;
            a[pos] = x;
            continue;
        }
        int l, r, x; cin >> l >> r >> x;
        for(int i=l; i<=r; i++){
            if(LCA(a[i], x) == x) b[i] = 1;
            else b[i] = 0;
        }
        bool done = 0;
        for(int i=l; i<=r; i++){
            if(!b[i]) continue;
            int las = i, nw = a[i];
            while(i+1<=r && b[i+1]){
                i++; nw = LCA(nw, a[i]);
            }
            if(nw == x){
                done = 1;
                cout << las << ' ' << i << '\n';
                break;
            }
        }
        if(!done) cout << "-1 -1\n"; 
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB n=5
2 Correct 2 ms 10588 KB n=100
3 Correct 2 ms 10588 KB n=100
4 Correct 2 ms 10584 KB n=100
5 Correct 2 ms 10588 KB n=100
6 Correct 2 ms 10588 KB n=100
7 Correct 2 ms 10588 KB n=100
8 Correct 2 ms 10584 KB n=100
9 Correct 1 ms 10588 KB n=100
10 Correct 2 ms 10588 KB n=100
11 Correct 2 ms 10584 KB n=100
12 Correct 2 ms 10584 KB n=100
13 Correct 1 ms 10588 KB n=100
14 Correct 2 ms 10584 KB n=100
15 Correct 1 ms 10588 KB n=100
16 Correct 2 ms 10588 KB n=100
17 Correct 2 ms 10584 KB n=100
18 Correct 1 ms 10588 KB n=100
19 Correct 2 ms 10588 KB n=100
20 Correct 1 ms 10588 KB n=100
21 Correct 2 ms 10588 KB n=100
22 Correct 2 ms 10588 KB n=100
23 Correct 2 ms 10588 KB n=100
24 Correct 2 ms 10588 KB n=100
25 Correct 2 ms 10588 KB n=100
26 Correct 1 ms 10680 KB n=12
27 Correct 2 ms 10588 KB n=100
28 Correct 7 ms 10588 KB n=500
29 Correct 5 ms 10584 KB n=500
30 Correct 5 ms 10588 KB n=500
31 Correct 5 ms 10584 KB n=500
32 Correct 8 ms 10588 KB n=500
33 Correct 5 ms 10772 KB n=500
34 Correct 8 ms 10588 KB n=500
35 Correct 5 ms 10588 KB n=500
36 Correct 19 ms 10584 KB n=500
37 Correct 16 ms 10588 KB n=500
38 Correct 19 ms 10584 KB n=500
39 Correct 6 ms 10772 KB n=500
40 Correct 6 ms 10588 KB n=500
41 Correct 5 ms 10588 KB n=500
42 Correct 11 ms 10840 KB n=500
43 Correct 11 ms 10764 KB n=500
44 Correct 10 ms 10588 KB n=500
45 Correct 7 ms 10588 KB n=500
46 Correct 5 ms 10588 KB n=500
47 Correct 4 ms 10588 KB n=500
48 Correct 6 ms 10588 KB n=500
49 Correct 4 ms 10584 KB n=500
50 Correct 6 ms 10764 KB n=500
51 Correct 6 ms 10584 KB n=500
52 Correct 5 ms 10588 KB n=500
53 Correct 5 ms 10588 KB n=500
54 Correct 16 ms 10588 KB n=500
55 Correct 3 ms 10588 KB n=278
56 Correct 14 ms 10588 KB n=500
57 Correct 14 ms 10584 KB n=500
58 Correct 13 ms 10588 KB n=500
59 Correct 95 ms 10844 KB n=2000
60 Correct 53 ms 10920 KB n=2000
61 Correct 56 ms 10844 KB n=2000
62 Correct 58 ms 10844 KB n=2000
63 Correct 102 ms 10844 KB n=2000
64 Correct 61 ms 10844 KB n=2000
65 Correct 100 ms 10868 KB n=2000
66 Correct 59 ms 10844 KB n=2000
67 Correct 87 ms 10844 KB n=2000
68 Correct 57 ms 10840 KB n=2000
69 Correct 263 ms 10840 KB n=2000
70 Correct 275 ms 11116 KB n=2000
71 Correct 239 ms 10880 KB n=2000
72 Correct 71 ms 10840 KB n=2000
73 Correct 74 ms 10844 KB n=2000
74 Correct 71 ms 10844 KB n=1844
75 Correct 84 ms 10844 KB n=2000
76 Correct 155 ms 10848 KB n=2000
77 Correct 153 ms 10872 KB n=2000
78 Correct 155 ms 10844 KB n=2000
79 Correct 82 ms 10840 KB n=2000
80 Correct 47 ms 10844 KB n=2000
81 Correct 57 ms 10872 KB n=2000
82 Correct 81 ms 10844 KB n=2000
83 Correct 46 ms 10840 KB n=2000
84 Correct 75 ms 10844 KB n=2000
85 Correct 75 ms 10840 KB n=2000
86 Correct 81 ms 10840 KB n=2000
87 Correct 78 ms 10864 KB n=2000
88 Correct 266 ms 10844 KB n=2000
89 Correct 265 ms 10896 KB n=2000
90 Correct 210 ms 10844 KB n=2000
91 Correct 183 ms 10864 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB n=5
2 Correct 2 ms 10588 KB n=100
3 Correct 2 ms 10588 KB n=100
4 Correct 2 ms 10584 KB n=100
5 Correct 2 ms 10588 KB n=100
6 Correct 2 ms 10588 KB n=100
7 Correct 2 ms 10588 KB n=100
8 Correct 2 ms 10584 KB n=100
9 Correct 1 ms 10588 KB n=100
10 Correct 2 ms 10588 KB n=100
11 Correct 2 ms 10584 KB n=100
12 Correct 2 ms 10584 KB n=100
13 Correct 1 ms 10588 KB n=100
14 Correct 2 ms 10584 KB n=100
15 Correct 1 ms 10588 KB n=100
16 Correct 2 ms 10588 KB n=100
17 Correct 2 ms 10584 KB n=100
18 Correct 1 ms 10588 KB n=100
19 Correct 2 ms 10588 KB n=100
20 Correct 1 ms 10588 KB n=100
21 Correct 2 ms 10588 KB n=100
22 Correct 2 ms 10588 KB n=100
23 Correct 2 ms 10588 KB n=100
24 Correct 2 ms 10588 KB n=100
25 Correct 2 ms 10588 KB n=100
26 Correct 1 ms 10680 KB n=12
27 Correct 2 ms 10588 KB n=100
28 Correct 7 ms 10588 KB n=500
29 Correct 5 ms 10584 KB n=500
30 Correct 5 ms 10588 KB n=500
31 Correct 5 ms 10584 KB n=500
32 Correct 8 ms 10588 KB n=500
33 Correct 5 ms 10772 KB n=500
34 Correct 8 ms 10588 KB n=500
35 Correct 5 ms 10588 KB n=500
36 Correct 19 ms 10584 KB n=500
37 Correct 16 ms 10588 KB n=500
38 Correct 19 ms 10584 KB n=500
39 Correct 6 ms 10772 KB n=500
40 Correct 6 ms 10588 KB n=500
41 Correct 5 ms 10588 KB n=500
42 Correct 11 ms 10840 KB n=500
43 Correct 11 ms 10764 KB n=500
44 Correct 10 ms 10588 KB n=500
45 Correct 7 ms 10588 KB n=500
46 Correct 5 ms 10588 KB n=500
47 Correct 4 ms 10588 KB n=500
48 Correct 6 ms 10588 KB n=500
49 Correct 4 ms 10584 KB n=500
50 Correct 6 ms 10764 KB n=500
51 Correct 6 ms 10584 KB n=500
52 Correct 5 ms 10588 KB n=500
53 Correct 5 ms 10588 KB n=500
54 Correct 16 ms 10588 KB n=500
55 Correct 3 ms 10588 KB n=278
56 Correct 14 ms 10588 KB n=500
57 Correct 14 ms 10584 KB n=500
58 Correct 13 ms 10588 KB n=500
59 Correct 95 ms 10844 KB n=2000
60 Correct 53 ms 10920 KB n=2000
61 Correct 56 ms 10844 KB n=2000
62 Correct 58 ms 10844 KB n=2000
63 Correct 102 ms 10844 KB n=2000
64 Correct 61 ms 10844 KB n=2000
65 Correct 100 ms 10868 KB n=2000
66 Correct 59 ms 10844 KB n=2000
67 Correct 87 ms 10844 KB n=2000
68 Correct 57 ms 10840 KB n=2000
69 Correct 263 ms 10840 KB n=2000
70 Correct 275 ms 11116 KB n=2000
71 Correct 239 ms 10880 KB n=2000
72 Correct 71 ms 10840 KB n=2000
73 Correct 74 ms 10844 KB n=2000
74 Correct 71 ms 10844 KB n=1844
75 Correct 84 ms 10844 KB n=2000
76 Correct 155 ms 10848 KB n=2000
77 Correct 153 ms 10872 KB n=2000
78 Correct 155 ms 10844 KB n=2000
79 Correct 82 ms 10840 KB n=2000
80 Correct 47 ms 10844 KB n=2000
81 Correct 57 ms 10872 KB n=2000
82 Correct 81 ms 10844 KB n=2000
83 Correct 46 ms 10840 KB n=2000
84 Correct 75 ms 10844 KB n=2000
85 Correct 75 ms 10840 KB n=2000
86 Correct 81 ms 10840 KB n=2000
87 Correct 78 ms 10864 KB n=2000
88 Correct 266 ms 10844 KB n=2000
89 Correct 265 ms 10896 KB n=2000
90 Correct 210 ms 10844 KB n=2000
91 Correct 183 ms 10864 KB n=2000
92 Execution timed out 4070 ms 57484 KB Time limit exceeded
93 Halted 0 ms 0 KB -