oj.uz

답안 #607721

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
607721 2022-07-27T01:46:03 Z bgnbvnbv Birthday gift (IZhO18_treearray) C++14
100 / 100
 1199 ms 111868 KB 
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll maxN=3e5+1;
vector<ll> g[maxN];
ll par[maxN][20],h[maxN],p[maxN];
void dfs(ll u, ll pp)
{
    for(auto v:g[u])
    {
        if(v!=pp)
        {
            p[v]=u;
            par[v][0]=u;
            h[v]=h[u]+1;
            for(int i=1;i<=18;i++) par[v][i]=par[par[v][i-1]][i-1];
            dfs(v,u);
        }
    }
}
ll LCA(ll u, ll v)
{
    if(h[u]<h[v]) swap(u,v);
    ll log=log2(h[u])+1;
    for(int i=log;i>=0;i--)
    {
        if(h[par[u][i]]>=h[v]) u=par[u][i];
    }
    if(u==v) return u;
    for(int i=log;i>=0;i--)
    {
        if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
    }
    return p[u];
}
ll n,m,q;
set<int> s[maxN],t[maxN];
ll a[maxN];
#define pb push_back
ll lca[maxN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    p[1]=1;
    for(int i=0;i<=18;i++) par[1][i]=1;
    dfs(1,0);
    for(int i=1;i<=m;i++) cin >> a[i],s[a[i]].insert(i);
    for(int i=1;i<m;i++)
    {
        lca[i]=LCA(a[i],a[i+1]);
        t[lca[i]].insert(i);
    }
    //for(auto z:t[1]) cout << z<<' ';
    //cout << '\n';
    for(int i=1;i<=q;i++)
    {
        ll type,l,r,k;
        cin >> type;
        if(type==1)
        {
            cin >> l >> r;
            s[a[l]].erase(l);
            t[lca[l]].erase(l);
            t[lca[l-1]].erase(l-1);
            a[l]=r;
            s[a[l]].insert(l);
            if(l<m)
            {
                lca[l]=LCA(a[l],a[l+1]);
                t[lca[l]].insert(l);
            }
            if(l>1)
            {
                lca[l-1]=LCA(a[l-1],a[l]);
                t[lca[l-1]].insert(l-1);
            }
        }
        else
        {
            cin >> l >> r >> k;
            auto x=s[k].upper_bound(l-1);
            if(*x<=r&&x!=s[k].end())
            {
                cout << *x <<' '<<*x<<'\n';
            }
            else
            {
                x=t[k].upper_bound(l-1);
                if(*x<=r-1&&x!=t[k].end())
                {
                    cout << *x<<' '<<*x+1<<'\n';

                }
                else
                {
                    cout <<-1<< ' '<<-1<<'\n';
                }
            }
        }
    }

}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 35540 KB n=5
2 Correct 20 ms 35544 KB n=100
3 Correct 16 ms 35480 KB n=100
4 Correct 18 ms 35596 KB n=100
5 Correct 17 ms 35540 KB n=100
6 Correct 17 ms 35492 KB n=100
7 Correct 18 ms 35540 KB n=100
8 Correct 18 ms 35540 KB n=100
9 Correct 17 ms 35600 KB n=100
10 Correct 19 ms 35500 KB n=100
11 Correct 18 ms 35540 KB n=100
12 Correct 21 ms 35552 KB n=100
13 Correct 19 ms 35568 KB n=100
14 Correct 17 ms 35540 KB n=100
15 Correct 17 ms 35596 KB n=100
16 Correct 17 ms 35540 KB n=100
17 Correct 16 ms 35540 KB n=100
18 Correct 17 ms 35484 KB n=100
19 Correct 20 ms 35512 KB n=100
20 Correct 17 ms 35540 KB n=100
21 Correct 16 ms 35608 KB n=100
22 Correct 17 ms 35536 KB n=100
23 Correct 17 ms 35540 KB n=100
24 Correct 16 ms 35540 KB n=100
25 Correct 16 ms 35540 KB n=100
26 Correct 18 ms 35540 KB n=12
27 Correct 21 ms 35604 KB n=100

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 35540 KB n=5
2 Correct 20 ms 35544 KB n=100
3 Correct 16 ms 35480 KB n=100
4 Correct 18 ms 35596 KB n=100
5 Correct 17 ms 35540 KB n=100
6 Correct 17 ms 35492 KB n=100
7 Correct 18 ms 35540 KB n=100
8 Correct 18 ms 35540 KB n=100
9 Correct 17 ms 35600 KB n=100
10 Correct 19 ms 35500 KB n=100
11 Correct 18 ms 35540 KB n=100
12 Correct 21 ms 35552 KB n=100
13 Correct 19 ms 35568 KB n=100
14 Correct 17 ms 35540 KB n=100
15 Correct 17 ms 35596 KB n=100
16 Correct 17 ms 35540 KB n=100
17 Correct 16 ms 35540 KB n=100
18 Correct 17 ms 35484 KB n=100
19 Correct 20 ms 35512 KB n=100
20 Correct 17 ms 35540 KB n=100
21 Correct 16 ms 35608 KB n=100
22 Correct 17 ms 35536 KB n=100
23 Correct 17 ms 35540 KB n=100
24 Correct 16 ms 35540 KB n=100
25 Correct 16 ms 35540 KB n=100
26 Correct 18 ms 35540 KB n=12
27 Correct 21 ms 35604 KB n=100
28 Correct 18 ms 35732 KB n=500
29 Correct 18 ms 35764 KB n=500
30 Correct 18 ms 35668 KB n=500
31 Correct 18 ms 35676 KB n=500
32 Correct 18 ms 35668 KB n=500
33 Correct 18 ms 35740 KB n=500
34 Correct 18 ms 35740 KB n=500
35 Correct 18 ms 35668 KB n=500
36 Correct 18 ms 35664 KB n=500
37 Correct 20 ms 35708 KB n=500
38 Correct 18 ms 35668 KB n=500
39 Correct 17 ms 35668 KB n=500
40 Correct 19 ms 35628 KB n=500
41 Correct 18 ms 35692 KB n=500
42 Correct 18 ms 35668 KB n=500
43 Correct 18 ms 35668 KB n=500
44 Correct 18 ms 35668 KB n=500
45 Correct 18 ms 35688 KB n=500
46 Correct 18 ms 35740 KB n=500
47 Correct 18 ms 35668 KB n=500
48 Correct 17 ms 35652 KB n=500
49 Correct 17 ms 35676 KB n=500
50 Correct 19 ms 35668 KB n=500
51 Correct 19 ms 35660 KB n=500
52 Correct 24 ms 35724 KB n=500
53 Correct 18 ms 35740 KB n=500
54 Correct 17 ms 35668 KB n=500
55 Correct 17 ms 35696 KB n=278
56 Correct 17 ms 35756 KB n=500
57 Correct 18 ms 35760 KB n=500
58 Correct 22 ms 35656 KB n=500

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 35540 KB n=5
2 Correct 20 ms 35544 KB n=100
3 Correct 16 ms 35480 KB n=100
4 Correct 18 ms 35596 KB n=100
5 Correct 17 ms 35540 KB n=100
6 Correct 17 ms 35492 KB n=100
7 Correct 18 ms 35540 KB n=100
8 Correct 18 ms 35540 KB n=100
9 Correct 17 ms 35600 KB n=100
10 Correct 19 ms 35500 KB n=100
11 Correct 18 ms 35540 KB n=100
12 Correct 21 ms 35552 KB n=100
13 Correct 19 ms 35568 KB n=100
14 Correct 17 ms 35540 KB n=100
15 Correct 17 ms 35596 KB n=100
16 Correct 17 ms 35540 KB n=100
17 Correct 16 ms 35540 KB n=100
18 Correct 17 ms 35484 KB n=100
19 Correct 20 ms 35512 KB n=100
20 Correct 17 ms 35540 KB n=100
21 Correct 16 ms 35608 KB n=100
22 Correct 17 ms 35536 KB n=100
23 Correct 17 ms 35540 KB n=100
24 Correct 16 ms 35540 KB n=100
25 Correct 16 ms 35540 KB n=100
26 Correct 18 ms 35540 KB n=12
27 Correct 21 ms 35604 KB n=100
28 Correct 18 ms 35732 KB n=500
29 Correct 18 ms 35764 KB n=500
30 Correct 18 ms 35668 KB n=500
31 Correct 18 ms 35676 KB n=500
32 Correct 18 ms 35668 KB n=500
33 Correct 18 ms 35740 KB n=500
34 Correct 18 ms 35740 KB n=500
35 Correct 18 ms 35668 KB n=500
36 Correct 18 ms 35664 KB n=500
37 Correct 20 ms 35708 KB n=500
38 Correct 18 ms 35668 KB n=500
39 Correct 17 ms 35668 KB n=500
40 Correct 19 ms 35628 KB n=500
41 Correct 18 ms 35692 KB n=500
42 Correct 18 ms 35668 KB n=500
43 Correct 18 ms 35668 KB n=500
44 Correct 18 ms 35668 KB n=500
45 Correct 18 ms 35688 KB n=500
46 Correct 18 ms 35740 KB n=500
47 Correct 18 ms 35668 KB n=500
48 Correct 17 ms 35652 KB n=500
49 Correct 17 ms 35676 KB n=500
50 Correct 19 ms 35668 KB n=500
51 Correct 19 ms 35660 KB n=500
52 Correct 24 ms 35724 KB n=500
53 Correct 18 ms 35740 KB n=500
54 Correct 17 ms 35668 KB n=500
55 Correct 17 ms 35696 KB n=278
56 Correct 17 ms 35756 KB n=500
57 Correct 18 ms 35760 KB n=500
58 Correct 22 ms 35656 KB n=500
59 Correct 19 ms 36180 KB n=2000
60 Correct 19 ms 36260 KB n=2000
61 Correct 20 ms 36284 KB n=2000
62 Correct 19 ms 36180 KB n=2000
63 Correct 20 ms 36180 KB n=2000
64 Correct 23 ms 36264 KB n=2000
65 Correct 21 ms 36128 KB n=2000
66 Correct 20 ms 36192 KB n=2000
67 Correct 20 ms 36224 KB n=2000
68 Correct 20 ms 36284 KB n=2000
69 Correct 20 ms 36132 KB n=2000
70 Correct 19 ms 36228 KB n=2000
71 Correct 19 ms 36180 KB n=2000
72 Correct 21 ms 36180 KB n=2000
73 Correct 20 ms 36196 KB n=2000
74 Correct 19 ms 36192 KB n=1844
75 Correct 19 ms 36180 KB n=2000
76 Correct 22 ms 36180 KB n=2000
77 Correct 20 ms 36148 KB n=2000
78 Correct 20 ms 36180 KB n=2000
79 Correct 20 ms 36220 KB n=2000
80 Correct 20 ms 36244 KB n=2000
81 Correct 20 ms 36264 KB n=2000
82 Correct 20 ms 36180 KB n=2000
83 Correct 20 ms 36296 KB n=2000
84 Correct 23 ms 36180 KB n=2000
85 Correct 22 ms 36228 KB n=2000
86 Correct 20 ms 36216 KB n=2000
87 Correct 23 ms 36116 KB n=2000
88 Correct 21 ms 36308 KB n=2000
89 Correct 21 ms 36300 KB n=2000
90 Correct 20 ms 36308 KB n=2000
91 Correct 23 ms 36180 KB n=2000

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 35540 KB n=5
2 Correct 20 ms 35544 KB n=100
3 Correct 16 ms 35480 KB n=100
4 Correct 18 ms 35596 KB n=100
5 Correct 17 ms 35540 KB n=100
6 Correct 17 ms 35492 KB n=100
7 Correct 18 ms 35540 KB n=100
8 Correct 18 ms 35540 KB n=100
9 Correct 17 ms 35600 KB n=100
10 Correct 19 ms 35500 KB n=100
11 Correct 18 ms 35540 KB n=100
12 Correct 21 ms 35552 KB n=100
13 Correct 19 ms 35568 KB n=100
14 Correct 17 ms 35540 KB n=100
15 Correct 17 ms 35596 KB n=100
16 Correct 17 ms 35540 KB n=100
17 Correct 16 ms 35540 KB n=100
18 Correct 17 ms 35484 KB n=100
19 Correct 20 ms 35512 KB n=100
20 Correct 17 ms 35540 KB n=100
21 Correct 16 ms 35608 KB n=100
22 Correct 17 ms 35536 KB n=100
23 Correct 17 ms 35540 KB n=100
24 Correct 16 ms 35540 KB n=100
25 Correct 16 ms 35540 KB n=100
26 Correct 18 ms 35540 KB n=12
27 Correct 21 ms 35604 KB n=100
28 Correct 18 ms 35732 KB n=500
29 Correct 18 ms 35764 KB n=500
30 Correct 18 ms 35668 KB n=500
31 Correct 18 ms 35676 KB n=500
32 Correct 18 ms 35668 KB n=500
33 Correct 18 ms 35740 KB n=500
34 Correct 18 ms 35740 KB n=500
35 Correct 18 ms 35668 KB n=500
36 Correct 18 ms 35664 KB n=500
37 Correct 20 ms 35708 KB n=500
38 Correct 18 ms 35668 KB n=500
39 Correct 17 ms 35668 KB n=500
40 Correct 19 ms 35628 KB n=500
41 Correct 18 ms 35692 KB n=500
42 Correct 18 ms 35668 KB n=500
43 Correct 18 ms 35668 KB n=500
44 Correct 18 ms 35668 KB n=500
45 Correct 18 ms 35688 KB n=500
46 Correct 18 ms 35740 KB n=500
47 Correct 18 ms 35668 KB n=500
48 Correct 17 ms 35652 KB n=500
49 Correct 17 ms 35676 KB n=500
50 Correct 19 ms 35668 KB n=500
51 Correct 19 ms 35660 KB n=500
52 Correct 24 ms 35724 KB n=500
53 Correct 18 ms 35740 KB n=500
54 Correct 17 ms 35668 KB n=500
55 Correct 17 ms 35696 KB n=278
56 Correct 17 ms 35756 KB n=500
57 Correct 18 ms 35760 KB n=500
58 Correct 22 ms 35656 KB n=500
59 Correct 19 ms 36180 KB n=2000
60 Correct 19 ms 36260 KB n=2000
61 Correct 20 ms 36284 KB n=2000
62 Correct 19 ms 36180 KB n=2000
63 Correct 20 ms 36180 KB n=2000
64 Correct 23 ms 36264 KB n=2000
65 Correct 21 ms 36128 KB n=2000
66 Correct 20 ms 36192 KB n=2000
67 Correct 20 ms 36224 KB n=2000
68 Correct 20 ms 36284 KB n=2000
69 Correct 20 ms 36132 KB n=2000
70 Correct 19 ms 36228 KB n=2000
71 Correct 19 ms 36180 KB n=2000
72 Correct 21 ms 36180 KB n=2000
73 Correct 20 ms 36196 KB n=2000
74 Correct 19 ms 36192 KB n=1844
75 Correct 19 ms 36180 KB n=2000
76 Correct 22 ms 36180 KB n=2000
77 Correct 20 ms 36148 KB n=2000
78 Correct 20 ms 36180 KB n=2000
79 Correct 20 ms 36220 KB n=2000
80 Correct 20 ms 36244 KB n=2000
81 Correct 20 ms 36264 KB n=2000
82 Correct 20 ms 36180 KB n=2000
83 Correct 20 ms 36296 KB n=2000
84 Correct 23 ms 36180 KB n=2000
85 Correct 22 ms 36228 KB n=2000
86 Correct 20 ms 36216 KB n=2000
87 Correct 23 ms 36116 KB n=2000
88 Correct 21 ms 36308 KB n=2000
89 Correct 21 ms 36300 KB n=2000
90 Correct 20 ms 36308 KB n=2000
91 Correct 23 ms 36180 KB n=2000
92 Correct 640 ms 100888 KB n=200000
93 Correct 1199 ms 106248 KB n=200000
94 Correct 1080 ms 110284 KB n=200000
95 Correct 621 ms 100836 KB n=200000
96 Correct 584 ms 100840 KB n=200000
97 Correct 1182 ms 105100 KB n=200000
98 Correct 592 ms 100820 KB n=200000
99 Correct 793 ms 100576 KB n=200000
100 Correct 656 ms 100996 KB n=200000
101 Correct 1025 ms 111648 KB n=200000
102 Correct 410 ms 101968 KB n=200000
103 Correct 410 ms 101996 KB n=200000
104 Correct 431 ms 102060 KB n=200000
105 Correct 410 ms 101656 KB n=200000
106 Correct 441 ms 101708 KB n=200000
107 Correct 401 ms 101712 KB n=200000
108 Correct 716 ms 100608 KB n=200000
109 Correct 754 ms 100672 KB n=200000
110 Correct 751 ms 100640 KB n=200000
111 Correct 597 ms 100752 KB n=200000
112 Correct 1035 ms 110504 KB n=200000
113 Correct 1091 ms 104960 KB n=200000
114 Correct 619 ms 100668 KB n=200000
115 Correct 1182 ms 102364 KB n=200000
116 Correct 581 ms 100592 KB n=200000
117 Correct 994 ms 111000 KB n=200000
118 Correct 1105 ms 103668 KB n=200000
119 Correct 561 ms 100588 KB n=200000
120 Correct 1004 ms 111396 KB n=200000
121 Correct 968 ms 111256 KB n=200000
122 Correct 947 ms 111868 KB n=200000
123 Correct 449 ms 101536 KB n=200000
124 Correct 234 ms 52324 KB n=25264