oj.uz

Submission #468539

# Submission time Handle Problem Language Result Execution time Memory
468539 2021-08-28T16:47:31 Z Killer2501 Birthday gift (IZhO18_treearray) C++14
100 / 100
 1178 ms 102312 KB 
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define task "tests"
#define pll pair<ll, ll>
#define pi pair<ll, pll>
#define fi first
#define se second

using namespace std;
const ll mod = 1e9+7;
const ll N = 2e5+5;
const int base = 313;
ll n, m, t, k, T, ans, q, tong, c[N], a[N], b[N], h[N], P[N][20];
vector<ll> adj[N], kq;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
set<ll> p1[N], p2[N];
void dfs(ll u, ll p)
{
    for(int i = 1; i < 20; i ++)P[u][i] = P[P[u][i-1]][i-1];
    for(ll v : adj[u])
    {
        if(v == p)continue;
        h[v] = h[u] + 1;
        P[v][0] = u;
        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[u] >= h[v] + (1<<i))u = P[u][i];
    if(u == v)return u;
    for(int i = log; i >= 0; i --)
    {
        if(P[u][i] && P[u][i] != P[v][i])
        {
            u = P[u][i];
            v = P[v][i];
        }
    }
    return P[u][0];
}
void sol()
{
    cin >> n >> m >> q;
    for(int i = 1; i < n; i ++)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i ++)
    {
        cin >> a[i];
        p1[a[i]].insert(i);
    }
    for(int i = 1; i < m; i ++)
    {
        b[i] = lca(a[i], a[i+1]);
        p2[b[i]].insert(i);
    }
    for(int i = 1; i <= n; i ++)
    {
        p1[i].insert(mod);
        p2[i].insert(mod);
    }
    while(q -- > 0)
    {
        ll l, r;
        cin >> t >> l >> r;
        if(t == 1)
        {
            p1[a[l]].erase(l);
            if(l < m)p2[b[l]].erase(l);
            if(l > 1)p2[b[l-1]].erase(l-1);
            a[l] = r;
            p1[r].insert(l);
            if(l < m)
            {
                b[l] = lca(a[l], a[l+1]);
                p2[b[l]].insert(l);
            }
            if(l > 1)
            {
                b[l-1] = lca(a[l-1], a[l]);
                p2[b[l-1]].insert(l-1);
            }
        }
        else
        {
            cin >> k;
            auto it = p1[k].lower_bound(l);
            if((*it) <= r)cout << (*it) <<" "<<(*it) << '\n';
            else
            {
                it = p2[k].lower_bound(l);
                if((*it)+1 <= r)cout << (*it) <<" "<<(*it)+1<<'\n';
                else cout << -1 <<" "<<-1 << '\n';
            }
        }
    }
}
int main()
{
    if(fopen(task".in", "r"))
    {
       freopen(task".in", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:120:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |        freopen(task".in", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:121:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB n=5
2 Correct 16 ms 23800 KB n=100
3 Correct 14 ms 23792 KB n=100
4 Correct 14 ms 23756 KB n=100
5 Correct 14 ms 23756 KB n=100
6 Correct 14 ms 23760 KB n=100
7 Correct 14 ms 23812 KB n=100
8 Correct 14 ms 23860 KB n=100
9 Correct 14 ms 23756 KB n=100
10 Correct 14 ms 23756 KB n=100
11 Correct 14 ms 23756 KB n=100
12 Correct 14 ms 23804 KB n=100
13 Correct 14 ms 23840 KB n=100
14 Correct 14 ms 23856 KB n=100
15 Correct 17 ms 23852 KB n=100
16 Correct 14 ms 23756 KB n=100
17 Correct 16 ms 23756 KB n=100
18 Correct 14 ms 23860 KB n=100
19 Correct 14 ms 23756 KB n=100
20 Correct 16 ms 23756 KB n=100
21 Correct 14 ms 23852 KB n=100
22 Correct 14 ms 23824 KB n=100
23 Correct 14 ms 23768 KB n=100
24 Correct 15 ms 23776 KB n=100
25 Correct 14 ms 23864 KB n=100
26 Correct 14 ms 23828 KB n=12
27 Correct 14 ms 23756 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB n=5
2 Correct 16 ms 23800 KB n=100
3 Correct 14 ms 23792 KB n=100
4 Correct 14 ms 23756 KB n=100
5 Correct 14 ms 23756 KB n=100
6 Correct 14 ms 23760 KB n=100
7 Correct 14 ms 23812 KB n=100
8 Correct 14 ms 23860 KB n=100
9 Correct 14 ms 23756 KB n=100
10 Correct 14 ms 23756 KB n=100
11 Correct 14 ms 23756 KB n=100
12 Correct 14 ms 23804 KB n=100
13 Correct 14 ms 23840 KB n=100
14 Correct 14 ms 23856 KB n=100
15 Correct 17 ms 23852 KB n=100
16 Correct 14 ms 23756 KB n=100
17 Correct 16 ms 23756 KB n=100
18 Correct 14 ms 23860 KB n=100
19 Correct 14 ms 23756 KB n=100
20 Correct 16 ms 23756 KB n=100
21 Correct 14 ms 23852 KB n=100
22 Correct 14 ms 23824 KB n=100
23 Correct 14 ms 23768 KB n=100
24 Correct 15 ms 23776 KB n=100
25 Correct 14 ms 23864 KB n=100
26 Correct 14 ms 23828 KB n=12
27 Correct 14 ms 23756 KB n=100
28 Correct 14 ms 23968 KB n=500
29 Correct 14 ms 24012 KB n=500
30 Correct 15 ms 23880 KB n=500
31 Correct 16 ms 23884 KB n=500
32 Correct 15 ms 23884 KB n=500
33 Correct 14 ms 23884 KB n=500
34 Correct 15 ms 23892 KB n=500
35 Correct 15 ms 23964 KB n=500
36 Correct 15 ms 23884 KB n=500
37 Correct 14 ms 23948 KB n=500
38 Correct 14 ms 23884 KB n=500
39 Correct 15 ms 23884 KB n=500
40 Correct 15 ms 23884 KB n=500
41 Correct 16 ms 24012 KB n=500
42 Correct 17 ms 23988 KB n=500
43 Correct 15 ms 24000 KB n=500
44 Correct 15 ms 23932 KB n=500
45 Correct 15 ms 23984 KB n=500
46 Correct 15 ms 24020 KB n=500
47 Correct 15 ms 24012 KB n=500
48 Correct 15 ms 23884 KB n=500
49 Correct 17 ms 24012 KB n=500
50 Correct 15 ms 23884 KB n=500
51 Correct 15 ms 23884 KB n=500
52 Correct 16 ms 23948 KB n=500
53 Correct 15 ms 23884 KB n=500
54 Correct 15 ms 24012 KB n=500
55 Correct 14 ms 23944 KB n=278
56 Correct 15 ms 23960 KB n=500
57 Correct 15 ms 23976 KB n=500
58 Correct 17 ms 23876 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB n=5
2 Correct 16 ms 23800 KB n=100
3 Correct 14 ms 23792 KB n=100
4 Correct 14 ms 23756 KB n=100
5 Correct 14 ms 23756 KB n=100
6 Correct 14 ms 23760 KB n=100
7 Correct 14 ms 23812 KB n=100
8 Correct 14 ms 23860 KB n=100
9 Correct 14 ms 23756 KB n=100
10 Correct 14 ms 23756 KB n=100
11 Correct 14 ms 23756 KB n=100
12 Correct 14 ms 23804 KB n=100
13 Correct 14 ms 23840 KB n=100
14 Correct 14 ms 23856 KB n=100
15 Correct 17 ms 23852 KB n=100
16 Correct 14 ms 23756 KB n=100
17 Correct 16 ms 23756 KB n=100
18 Correct 14 ms 23860 KB n=100
19 Correct 14 ms 23756 KB n=100
20 Correct 16 ms 23756 KB n=100
21 Correct 14 ms 23852 KB n=100
22 Correct 14 ms 23824 KB n=100
23 Correct 14 ms 23768 KB n=100
24 Correct 15 ms 23776 KB n=100
25 Correct 14 ms 23864 KB n=100
26 Correct 14 ms 23828 KB n=12
27 Correct 14 ms 23756 KB n=100
28 Correct 14 ms 23968 KB n=500
29 Correct 14 ms 24012 KB n=500
30 Correct 15 ms 23880 KB n=500
31 Correct 16 ms 23884 KB n=500
32 Correct 15 ms 23884 KB n=500
33 Correct 14 ms 23884 KB n=500
34 Correct 15 ms 23892 KB n=500
35 Correct 15 ms 23964 KB n=500
36 Correct 15 ms 23884 KB n=500
37 Correct 14 ms 23948 KB n=500
38 Correct 14 ms 23884 KB n=500
39 Correct 15 ms 23884 KB n=500
40 Correct 15 ms 23884 KB n=500
41 Correct 16 ms 24012 KB n=500
42 Correct 17 ms 23988 KB n=500
43 Correct 15 ms 24000 KB n=500
44 Correct 15 ms 23932 KB n=500
45 Correct 15 ms 23984 KB n=500
46 Correct 15 ms 24020 KB n=500
47 Correct 15 ms 24012 KB n=500
48 Correct 15 ms 23884 KB n=500
49 Correct 17 ms 24012 KB n=500
50 Correct 15 ms 23884 KB n=500
51 Correct 15 ms 23884 KB n=500
52 Correct 16 ms 23948 KB n=500
53 Correct 15 ms 23884 KB n=500
54 Correct 15 ms 24012 KB n=500
55 Correct 14 ms 23944 KB n=278
56 Correct 15 ms 23960 KB n=500
57 Correct 15 ms 23976 KB n=500
58 Correct 17 ms 23876 KB n=500
59 Correct 17 ms 24396 KB n=2000
60 Correct 18 ms 24612 KB n=2000
61 Correct 20 ms 24524 KB n=2000
62 Correct 19 ms 24412 KB n=2000
63 Correct 18 ms 24452 KB n=2000
64 Correct 18 ms 24472 KB n=2000
65 Correct 17 ms 24396 KB n=2000
66 Correct 19 ms 24552 KB n=2000
67 Correct 19 ms 24372 KB n=2000
68 Correct 18 ms 24524 KB n=2000
69 Correct 18 ms 24468 KB n=2000
70 Correct 18 ms 24448 KB n=2000
71 Correct 17 ms 24348 KB n=2000
72 Correct 18 ms 24440 KB n=2000
73 Correct 20 ms 24396 KB n=2000
74 Correct 17 ms 24396 KB n=1844
75 Correct 17 ms 24396 KB n=2000
76 Correct 18 ms 24396 KB n=2000
77 Correct 18 ms 24348 KB n=2000
78 Correct 18 ms 24396 KB n=2000
79 Correct 17 ms 24452 KB n=2000
80 Correct 18 ms 24576 KB n=2000
81 Correct 19 ms 24404 KB n=2000
82 Correct 18 ms 24396 KB n=2000
83 Correct 21 ms 24524 KB n=2000
84 Correct 19 ms 24464 KB n=2000
85 Correct 19 ms 24496 KB n=2000
86 Correct 21 ms 24396 KB n=2000
87 Correct 18 ms 24452 KB n=2000
88 Correct 22 ms 24596 KB n=2000
89 Correct 18 ms 24524 KB n=2000
90 Correct 19 ms 24524 KB n=2000
91 Correct 18 ms 24460 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB n=5
2 Correct 16 ms 23800 KB n=100
3 Correct 14 ms 23792 KB n=100
4 Correct 14 ms 23756 KB n=100
5 Correct 14 ms 23756 KB n=100
6 Correct 14 ms 23760 KB n=100
7 Correct 14 ms 23812 KB n=100
8 Correct 14 ms 23860 KB n=100
9 Correct 14 ms 23756 KB n=100
10 Correct 14 ms 23756 KB n=100
11 Correct 14 ms 23756 KB n=100
12 Correct 14 ms 23804 KB n=100
13 Correct 14 ms 23840 KB n=100
14 Correct 14 ms 23856 KB n=100
15 Correct 17 ms 23852 KB n=100
16 Correct 14 ms 23756 KB n=100
17 Correct 16 ms 23756 KB n=100
18 Correct 14 ms 23860 KB n=100
19 Correct 14 ms 23756 KB n=100
20 Correct 16 ms 23756 KB n=100
21 Correct 14 ms 23852 KB n=100
22 Correct 14 ms 23824 KB n=100
23 Correct 14 ms 23768 KB n=100
24 Correct 15 ms 23776 KB n=100
25 Correct 14 ms 23864 KB n=100
26 Correct 14 ms 23828 KB n=12
27 Correct 14 ms 23756 KB n=100
28 Correct 14 ms 23968 KB n=500
29 Correct 14 ms 24012 KB n=500
30 Correct 15 ms 23880 KB n=500
31 Correct 16 ms 23884 KB n=500
32 Correct 15 ms 23884 KB n=500
33 Correct 14 ms 23884 KB n=500
34 Correct 15 ms 23892 KB n=500
35 Correct 15 ms 23964 KB n=500
36 Correct 15 ms 23884 KB n=500
37 Correct 14 ms 23948 KB n=500
38 Correct 14 ms 23884 KB n=500
39 Correct 15 ms 23884 KB n=500
40 Correct 15 ms 23884 KB n=500
41 Correct 16 ms 24012 KB n=500
42 Correct 17 ms 23988 KB n=500
43 Correct 15 ms 24000 KB n=500
44 Correct 15 ms 23932 KB n=500
45 Correct 15 ms 23984 KB n=500
46 Correct 15 ms 24020 KB n=500
47 Correct 15 ms 24012 KB n=500
48 Correct 15 ms 23884 KB n=500
49 Correct 17 ms 24012 KB n=500
50 Correct 15 ms 23884 KB n=500
51 Correct 15 ms 23884 KB n=500
52 Correct 16 ms 23948 KB n=500
53 Correct 15 ms 23884 KB n=500
54 Correct 15 ms 24012 KB n=500
55 Correct 14 ms 23944 KB n=278
56 Correct 15 ms 23960 KB n=500
57 Correct 15 ms 23976 KB n=500
58 Correct 17 ms 23876 KB n=500
59 Correct 17 ms 24396 KB n=2000
60 Correct 18 ms 24612 KB n=2000
61 Correct 20 ms 24524 KB n=2000
62 Correct 19 ms 24412 KB n=2000
63 Correct 18 ms 24452 KB n=2000
64 Correct 18 ms 24472 KB n=2000
65 Correct 17 ms 24396 KB n=2000
66 Correct 19 ms 24552 KB n=2000
67 Correct 19 ms 24372 KB n=2000
68 Correct 18 ms 24524 KB n=2000
69 Correct 18 ms 24468 KB n=2000
70 Correct 18 ms 24448 KB n=2000
71 Correct 17 ms 24348 KB n=2000
72 Correct 18 ms 24440 KB n=2000
73 Correct 20 ms 24396 KB n=2000
74 Correct 17 ms 24396 KB n=1844
75 Correct 17 ms 24396 KB n=2000
76 Correct 18 ms 24396 KB n=2000
77 Correct 18 ms 24348 KB n=2000
78 Correct 18 ms 24396 KB n=2000
79 Correct 17 ms 24452 KB n=2000
80 Correct 18 ms 24576 KB n=2000
81 Correct 19 ms 24404 KB n=2000
82 Correct 18 ms 24396 KB n=2000
83 Correct 21 ms 24524 KB n=2000
84 Correct 19 ms 24464 KB n=2000
85 Correct 19 ms 24496 KB n=2000
86 Correct 21 ms 24396 KB n=2000
87 Correct 18 ms 24452 KB n=2000
88 Correct 22 ms 24596 KB n=2000
89 Correct 18 ms 24524 KB n=2000
90 Correct 19 ms 24524 KB n=2000
91 Correct 18 ms 24460 KB n=2000
92 Correct 885 ms 87572 KB n=200000
93 Correct 1132 ms 94376 KB n=200000
94 Correct 1083 ms 100076 KB n=200000
95 Correct 790 ms 87588 KB n=200000
96 Correct 796 ms 87724 KB n=200000
97 Correct 1118 ms 92860 KB n=200000
98 Correct 763 ms 87564 KB n=200000
99 Correct 908 ms 86920 KB n=200000
100 Correct 783 ms 87692 KB n=200000
101 Correct 1054 ms 102120 KB n=200000
102 Correct 521 ms 88452 KB n=200000
103 Correct 546 ms 88392 KB n=200000
104 Correct 504 ms 88504 KB n=200000
105 Correct 513 ms 88236 KB n=200000
106 Correct 503 ms 88132 KB n=200000
107 Correct 539 ms 88136 KB n=200000
108 Correct 881 ms 87360 KB n=200000
109 Correct 872 ms 87160 KB n=200000
110 Correct 899 ms 87284 KB n=200000
111 Correct 743 ms 87436 KB n=200000
112 Correct 1047 ms 100404 KB n=200000
113 Correct 1098 ms 93104 KB n=200000
114 Correct 863 ms 87440 KB n=200000
115 Correct 1176 ms 89324 KB n=200000
116 Correct 839 ms 87204 KB n=200000
117 Correct 1106 ms 101096 KB n=200000
118 Correct 1178 ms 91020 KB n=200000
119 Correct 788 ms 87228 KB n=200000
120 Correct 1035 ms 101852 KB n=200000
121 Correct 995 ms 101892 KB n=200000
122 Correct 1093 ms 102312 KB n=200000
123 Correct 517 ms 87876 KB n=200000
124 Correct 245 ms 40172 KB n=25264