oj.uz

Submission #440638

# Submission time Handle Problem Language Result Execution time Memory
440638 2021-07-02T15:15:47 Z leaked Birthday gift (IZhO18_treearray) C++17
100 / 100
 1202 ms 83152 KB 
#include <bits/stdc++.h>

#define m_p make_pair
#define vec vector
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define f first
#define s second

using namespace std;
const int N=2e5+1;
const int lg=18;
vec<int> g[N];
int tin[N],tout[N],tt=1,up[N][lg];
set<int>st[N];
set<int>sob[N];
int vs[N];
void dfs(int v,int p){
    tin[v]=tt++;
    up[v][0]=p;
    for(int i=1;i<lg;i++) up[v][i]=up[up[v][i-1]][i-1];
    for(auto &z : g[v]){
        if(z==p) continue;
        dfs(z,v);
    }
    tout[v]=tt-1;
}
bool is(int a,int b){
    return tin[a]<=tin[b]&&tout[a]>=tout[b];
}
int lca(int a,int b){
    if(is(a,b)) return a;
    if(is(b,a)) return b;
    for(int i=lg-1;i>=0;i--){
        if(!is(up[a][i],b)) a=up[a][i];
    }
    return up[a][0];
}
/// [i,i+1]
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb(u);g[u].pb(v);
    }
    dfs(0,0);
    for(int i=0;i<m;i++){
        cin>>vs[i];--vs[i];
        sob[vs[i]].insert(i);
        if(i) st[lca(vs[i],vs[i-1])].insert(i-1);
    }
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int id,v;
            cin>>id>>v;--v;--id;
            if(id) st[lca(vs[id-1],vs[id])].erase(id-1);
            sob[vs[id]].erase(id);
            if(id+1<m) st[lca(vs[id+1],vs[id])].erase(id);
            vs[id]=v;
            if(id) st[lca(vs[id-1],vs[id])].insert(id-1);
            sob[vs[id]].insert(id);
            if(id+1<m) st[lca(vs[id+1],vs[id])].insert(id);
        }
        else{
            int l,r,v;
            cin>>l>>r>>v;
            --l;--r;--v;
            int x=-1,y=-1;
            auto it=sob[v].lower_bound(l);
            if(it!=sob[v].end() && *it<=r){
                x=*it;y=*it;
                x++;y++;
            }
            it=st[v].lower_bound(l);
            if(it!=st[v].end() && (*it)+1<=r){
                x=*it;y=*it+1;
                x++;y++;
            }
            cout<<x<<' '<<y<<'\n';
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB n=5
2 Correct 13 ms 23732 KB n=100
3 Correct 13 ms 23852 KB n=100
4 Correct 13 ms 23816 KB n=100
5 Correct 13 ms 23888 KB n=100
6 Correct 13 ms 23844 KB n=100
7 Correct 13 ms 23756 KB n=100
8 Correct 13 ms 23756 KB n=100
9 Correct 13 ms 23820 KB n=100
10 Correct 13 ms 23808 KB n=100
11 Correct 14 ms 23756 KB n=100
12 Correct 13 ms 23816 KB n=100
13 Correct 14 ms 23748 KB n=100
14 Correct 14 ms 23756 KB n=100
15 Correct 13 ms 23744 KB n=100
16 Correct 13 ms 23756 KB n=100
17 Correct 13 ms 23872 KB n=100
18 Correct 13 ms 23816 KB n=100
19 Correct 13 ms 23756 KB n=100
20 Correct 14 ms 23756 KB n=100
21 Correct 15 ms 23836 KB n=100
22 Correct 13 ms 23792 KB n=100
23 Correct 13 ms 23820 KB n=100
24 Correct 15 ms 23848 KB n=100
25 Correct 13 ms 23816 KB n=100
26 Correct 14 ms 23816 KB n=12
27 Correct 13 ms 23756 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB n=5
2 Correct 13 ms 23732 KB n=100
3 Correct 13 ms 23852 KB n=100
4 Correct 13 ms 23816 KB n=100
5 Correct 13 ms 23888 KB n=100
6 Correct 13 ms 23844 KB n=100
7 Correct 13 ms 23756 KB n=100
8 Correct 13 ms 23756 KB n=100
9 Correct 13 ms 23820 KB n=100
10 Correct 13 ms 23808 KB n=100
11 Correct 14 ms 23756 KB n=100
12 Correct 13 ms 23816 KB n=100
13 Correct 14 ms 23748 KB n=100
14 Correct 14 ms 23756 KB n=100
15 Correct 13 ms 23744 KB n=100
16 Correct 13 ms 23756 KB n=100
17 Correct 13 ms 23872 KB n=100
18 Correct 13 ms 23816 KB n=100
19 Correct 13 ms 23756 KB n=100
20 Correct 14 ms 23756 KB n=100
21 Correct 15 ms 23836 KB n=100
22 Correct 13 ms 23792 KB n=100
23 Correct 13 ms 23820 KB n=100
24 Correct 15 ms 23848 KB n=100
25 Correct 13 ms 23816 KB n=100
26 Correct 14 ms 23816 KB n=12
27 Correct 13 ms 23756 KB n=100
28 Correct 16 ms 23908 KB n=500
29 Correct 15 ms 23916 KB n=500
30 Correct 14 ms 23912 KB n=500
31 Correct 15 ms 23884 KB n=500
32 Correct 17 ms 23884 KB n=500
33 Correct 14 ms 23868 KB n=500
34 Correct 14 ms 23908 KB n=500
35 Correct 13 ms 23884 KB n=500
36 Correct 14 ms 23932 KB n=500
37 Correct 14 ms 23884 KB n=500
38 Correct 14 ms 23884 KB n=500
39 Correct 14 ms 23828 KB n=500
40 Correct 16 ms 23948 KB n=500
41 Correct 14 ms 23936 KB n=500
42 Correct 14 ms 23820 KB n=500
43 Correct 14 ms 23836 KB n=500
44 Correct 16 ms 23884 KB n=500
45 Correct 14 ms 23820 KB n=500
46 Correct 14 ms 23884 KB n=500
47 Correct 14 ms 23856 KB n=500
48 Correct 14 ms 23884 KB n=500
49 Correct 14 ms 23856 KB n=500
50 Correct 15 ms 23904 KB n=500
51 Correct 15 ms 23884 KB n=500
52 Correct 14 ms 23960 KB n=500
53 Correct 14 ms 23928 KB n=500
54 Correct 14 ms 23952 KB n=500
55 Correct 13 ms 23816 KB n=278
56 Correct 14 ms 23884 KB n=500
57 Correct 13 ms 23884 KB n=500
58 Correct 14 ms 23884 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB n=5
2 Correct 13 ms 23732 KB n=100
3 Correct 13 ms 23852 KB n=100
4 Correct 13 ms 23816 KB n=100
5 Correct 13 ms 23888 KB n=100
6 Correct 13 ms 23844 KB n=100
7 Correct 13 ms 23756 KB n=100
8 Correct 13 ms 23756 KB n=100
9 Correct 13 ms 23820 KB n=100
10 Correct 13 ms 23808 KB n=100
11 Correct 14 ms 23756 KB n=100
12 Correct 13 ms 23816 KB n=100
13 Correct 14 ms 23748 KB n=100
14 Correct 14 ms 23756 KB n=100
15 Correct 13 ms 23744 KB n=100
16 Correct 13 ms 23756 KB n=100
17 Correct 13 ms 23872 KB n=100
18 Correct 13 ms 23816 KB n=100
19 Correct 13 ms 23756 KB n=100
20 Correct 14 ms 23756 KB n=100
21 Correct 15 ms 23836 KB n=100
22 Correct 13 ms 23792 KB n=100
23 Correct 13 ms 23820 KB n=100
24 Correct 15 ms 23848 KB n=100
25 Correct 13 ms 23816 KB n=100
26 Correct 14 ms 23816 KB n=12
27 Correct 13 ms 23756 KB n=100
28 Correct 16 ms 23908 KB n=500
29 Correct 15 ms 23916 KB n=500
30 Correct 14 ms 23912 KB n=500
31 Correct 15 ms 23884 KB n=500
32 Correct 17 ms 23884 KB n=500
33 Correct 14 ms 23868 KB n=500
34 Correct 14 ms 23908 KB n=500
35 Correct 13 ms 23884 KB n=500
36 Correct 14 ms 23932 KB n=500
37 Correct 14 ms 23884 KB n=500
38 Correct 14 ms 23884 KB n=500
39 Correct 14 ms 23828 KB n=500
40 Correct 16 ms 23948 KB n=500
41 Correct 14 ms 23936 KB n=500
42 Correct 14 ms 23820 KB n=500
43 Correct 14 ms 23836 KB n=500
44 Correct 16 ms 23884 KB n=500
45 Correct 14 ms 23820 KB n=500
46 Correct 14 ms 23884 KB n=500
47 Correct 14 ms 23856 KB n=500
48 Correct 14 ms 23884 KB n=500
49 Correct 14 ms 23856 KB n=500
50 Correct 15 ms 23904 KB n=500
51 Correct 15 ms 23884 KB n=500
52 Correct 14 ms 23960 KB n=500
53 Correct 14 ms 23928 KB n=500
54 Correct 14 ms 23952 KB n=500
55 Correct 13 ms 23816 KB n=278
56 Correct 14 ms 23884 KB n=500
57 Correct 13 ms 23884 KB n=500
58 Correct 14 ms 23884 KB n=500
59 Correct 17 ms 24220 KB n=2000
60 Correct 16 ms 24364 KB n=2000
61 Correct 18 ms 24268 KB n=2000
62 Correct 17 ms 24268 KB n=2000
63 Correct 17 ms 24212 KB n=2000
64 Correct 17 ms 24268 KB n=2000
65 Correct 18 ms 24268 KB n=2000
66 Correct 17 ms 24496 KB n=2000
67 Correct 17 ms 24212 KB n=2000
68 Correct 17 ms 24348 KB n=2000
69 Correct 17 ms 24220 KB n=2000
70 Correct 17 ms 24308 KB n=2000
71 Correct 16 ms 24268 KB n=2000
72 Correct 17 ms 24256 KB n=2000
73 Correct 17 ms 24268 KB n=2000
74 Correct 17 ms 24392 KB n=1844
75 Correct 17 ms 24208 KB n=2000
76 Correct 18 ms 24268 KB n=2000
77 Correct 17 ms 24268 KB n=2000
78 Correct 17 ms 24296 KB n=2000
79 Correct 17 ms 24208 KB n=2000
80 Correct 17 ms 24424 KB n=2000
81 Correct 17 ms 24268 KB n=2000
82 Correct 17 ms 24212 KB n=2000
83 Correct 16 ms 24268 KB n=2000
84 Correct 17 ms 24272 KB n=2000
85 Correct 17 ms 24340 KB n=2000
86 Correct 19 ms 24240 KB n=2000
87 Correct 18 ms 24268 KB n=2000
88 Correct 16 ms 24396 KB n=2000
89 Correct 16 ms 24468 KB n=2000
90 Correct 17 ms 24340 KB n=2000
91 Correct 17 ms 24268 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB n=5
2 Correct 13 ms 23732 KB n=100
3 Correct 13 ms 23852 KB n=100
4 Correct 13 ms 23816 KB n=100
5 Correct 13 ms 23888 KB n=100
6 Correct 13 ms 23844 KB n=100
7 Correct 13 ms 23756 KB n=100
8 Correct 13 ms 23756 KB n=100
9 Correct 13 ms 23820 KB n=100
10 Correct 13 ms 23808 KB n=100
11 Correct 14 ms 23756 KB n=100
12 Correct 13 ms 23816 KB n=100
13 Correct 14 ms 23748 KB n=100
14 Correct 14 ms 23756 KB n=100
15 Correct 13 ms 23744 KB n=100
16 Correct 13 ms 23756 KB n=100
17 Correct 13 ms 23872 KB n=100
18 Correct 13 ms 23816 KB n=100
19 Correct 13 ms 23756 KB n=100
20 Correct 14 ms 23756 KB n=100
21 Correct 15 ms 23836 KB n=100
22 Correct 13 ms 23792 KB n=100
23 Correct 13 ms 23820 KB n=100
24 Correct 15 ms 23848 KB n=100
25 Correct 13 ms 23816 KB n=100
26 Correct 14 ms 23816 KB n=12
27 Correct 13 ms 23756 KB n=100
28 Correct 16 ms 23908 KB n=500
29 Correct 15 ms 23916 KB n=500
30 Correct 14 ms 23912 KB n=500
31 Correct 15 ms 23884 KB n=500
32 Correct 17 ms 23884 KB n=500
33 Correct 14 ms 23868 KB n=500
34 Correct 14 ms 23908 KB n=500
35 Correct 13 ms 23884 KB n=500
36 Correct 14 ms 23932 KB n=500
37 Correct 14 ms 23884 KB n=500
38 Correct 14 ms 23884 KB n=500
39 Correct 14 ms 23828 KB n=500
40 Correct 16 ms 23948 KB n=500
41 Correct 14 ms 23936 KB n=500
42 Correct 14 ms 23820 KB n=500
43 Correct 14 ms 23836 KB n=500
44 Correct 16 ms 23884 KB n=500
45 Correct 14 ms 23820 KB n=500
46 Correct 14 ms 23884 KB n=500
47 Correct 14 ms 23856 KB n=500
48 Correct 14 ms 23884 KB n=500
49 Correct 14 ms 23856 KB n=500
50 Correct 15 ms 23904 KB n=500
51 Correct 15 ms 23884 KB n=500
52 Correct 14 ms 23960 KB n=500
53 Correct 14 ms 23928 KB n=500
54 Correct 14 ms 23952 KB n=500
55 Correct 13 ms 23816 KB n=278
56 Correct 14 ms 23884 KB n=500
57 Correct 13 ms 23884 KB n=500
58 Correct 14 ms 23884 KB n=500
59 Correct 17 ms 24220 KB n=2000
60 Correct 16 ms 24364 KB n=2000
61 Correct 18 ms 24268 KB n=2000
62 Correct 17 ms 24268 KB n=2000
63 Correct 17 ms 24212 KB n=2000
64 Correct 17 ms 24268 KB n=2000
65 Correct 18 ms 24268 KB n=2000
66 Correct 17 ms 24496 KB n=2000
67 Correct 17 ms 24212 KB n=2000
68 Correct 17 ms 24348 KB n=2000
69 Correct 17 ms 24220 KB n=2000
70 Correct 17 ms 24308 KB n=2000
71 Correct 16 ms 24268 KB n=2000
72 Correct 17 ms 24256 KB n=2000
73 Correct 17 ms 24268 KB n=2000
74 Correct 17 ms 24392 KB n=1844
75 Correct 17 ms 24208 KB n=2000
76 Correct 18 ms 24268 KB n=2000
77 Correct 17 ms 24268 KB n=2000
78 Correct 17 ms 24296 KB n=2000
79 Correct 17 ms 24208 KB n=2000
80 Correct 17 ms 24424 KB n=2000
81 Correct 17 ms 24268 KB n=2000
82 Correct 17 ms 24212 KB n=2000
83 Correct 16 ms 24268 KB n=2000
84 Correct 17 ms 24272 KB n=2000
85 Correct 17 ms 24340 KB n=2000
86 Correct 19 ms 24240 KB n=2000
87 Correct 18 ms 24268 KB n=2000
88 Correct 16 ms 24396 KB n=2000
89 Correct 16 ms 24468 KB n=2000
90 Correct 17 ms 24340 KB n=2000
91 Correct 17 ms 24268 KB n=2000
92 Correct 882 ms 73760 KB n=200000
93 Correct 971 ms 78588 KB n=200000
94 Correct 680 ms 82008 KB n=200000
95 Correct 836 ms 73464 KB n=200000
96 Correct 853 ms 73608 KB n=200000
97 Correct 1025 ms 77720 KB n=200000
98 Correct 874 ms 73468 KB n=200000
99 Correct 1022 ms 73740 KB n=200000
100 Correct 876 ms 73552 KB n=200000
101 Correct 641 ms 83152 KB n=200000
102 Correct 537 ms 74772 KB n=200000
103 Correct 529 ms 74748 KB n=200000
104 Correct 536 ms 74804 KB n=200000
105 Correct 534 ms 75260 KB n=200000
106 Correct 520 ms 75224 KB n=200000
107 Correct 535 ms 75232 KB n=200000
108 Correct 906 ms 73604 KB n=200000
109 Correct 900 ms 73732 KB n=200000
110 Correct 892 ms 73720 KB n=200000
111 Correct 878 ms 73172 KB n=200000
112 Correct 669 ms 82168 KB n=200000
113 Correct 927 ms 77824 KB n=200000
114 Correct 927 ms 73184 KB n=200000
115 Correct 1202 ms 75528 KB n=200000
116 Correct 791 ms 73748 KB n=200000
117 Correct 696 ms 82596 KB n=200000
118 Correct 1092 ms 76600 KB n=200000
119 Correct 857 ms 73716 KB n=200000
120 Correct 636 ms 82208 KB n=200000
121 Correct 620 ms 82208 KB n=200000
122 Correct 632 ms 82496 KB n=200000
123 Correct 575 ms 74908 KB n=200000
124 Correct 204 ms 38520 KB n=25264