oj.uz

Submission #885355

# Submission time Handle Problem Language Result Execution time Memory
885355 2023-12-09T14:14:39 Z cpptowin Birthday gift (IZhO18_treearray) C++17
100 / 100
 903 ms 202228 KB 
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
using namespace std;
vi ke[maxn];
set<int> s1[maxn],s2[maxn];
int n,m,a[maxn],q;
int h[maxn],par[maxn][20];
void dfs(int u,int parent)
{
    for(int v : ke[u])
    {
        if(v == parent) continue;
        h[v] = h[u] + 1;
        par[v][0] = u;
        dfs(v,u);
    }
}
int lca(int u,int v)
{
    if(h[u] < h[v]) swap(u,v);
    int del = h[u] - h[v];
    fod(i,19,0) if(bit(del,i)) u = par[u][i];
    if(u == v) return u;
    fod(i,19,0) if(par[u][i] != par[v][i])
    {
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}
main()
{
    #define name "TASK"
    if(fopen(name".inp","r"))
    {
       freopen(name".inp","r",stdin);
       freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> m >> q;
    fo(i,1,n - 1)
    {
        int u,v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    dfs(1,1);
    fo(j,1,19) fo(i,1,n) par[i][j] = par[par[i][j - 1]][j - 1];
    fo(i,1,m)
    {
        cin >> a[i];
        s1[a[i]].insert(i);
    }
    fo(i,1,m - 1)
    {
        s2[lca(a[i],a[i + 1])].insert(i);
    }
    while(q--)
    {
        int type;
        cin >> type;
        if(type == 1)
        {
            int pos,v;
            cin >> pos >> v;
            auto lb = s1[a[pos]].lower_bound(pos);
            s1[a[pos]].erase(lb);
            s1[v].insert(pos);
            if(pos > 1)
            {
                int _lca = lca(a[pos],a[pos - 1]);
                lb = s2[_lca].lower_bound(pos - 1);
                s2[_lca].erase(lb);
                _lca = lca(v,a[pos - 1]);
                s2[_lca].insert(pos - 1);
            }
            if(pos < m)
            {
                int _lca = lca(a[pos],a[pos + 1]);
                lb = s2[_lca].lower_bound(pos);
                s2[_lca].erase(lb);
                _lca = lca(v,a[pos + 1]);
                s2[_lca].insert(pos);
            }
            a[pos] = v;
        }
        else 
        {
            int l,r,v;
            cin >> l >> r >> v;
            auto lb = s1[v].lower_bound(l);
            if(lb != s1[v].end() and *lb >= l and *lb <= r) cout << *lb << ' ' << *lb << "\n";
            else 
            {
                lb = s2[v].lower_bound(l);
                if(*lb >= l and *lb < r) cout << *lb << ' ' << *lb + 1 << "\n";
                else cout << -1 << ' ' << -1 << "\n";
            }
        }
    }
}

Compilation message

treearray.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main()
      | ^~~~
treearray.cpp: In function 'int main()':
treearray.cpp:54:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |        freopen(name".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:55:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |        freopen(name".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 121644 KB n=5
2 Correct 25 ms 121688 KB n=100
3 Correct 29 ms 121692 KB n=100
4 Correct 36 ms 121440 KB n=100
5 Correct 28 ms 121700 KB n=100
6 Correct 25 ms 121688 KB n=100
7 Correct 25 ms 121688 KB n=100
8 Correct 28 ms 121428 KB n=100
9 Correct 28 ms 121648 KB n=100
10 Correct 31 ms 121688 KB n=100
11 Correct 25 ms 121688 KB n=100
12 Correct 25 ms 121692 KB n=100
13 Correct 26 ms 121692 KB n=100
14 Correct 25 ms 121692 KB n=100
15 Correct 24 ms 121688 KB n=100
16 Correct 24 ms 121688 KB n=100
17 Correct 27 ms 121692 KB n=100
18 Correct 26 ms 121688 KB n=100
19 Correct 25 ms 121528 KB n=100
20 Correct 24 ms 121688 KB n=100
21 Correct 24 ms 121692 KB n=100
22 Correct 25 ms 121692 KB n=100
23 Correct 24 ms 121656 KB n=100
24 Correct 26 ms 121516 KB n=100
25 Correct 25 ms 121464 KB n=100
26 Correct 25 ms 121436 KB n=12
27 Correct 24 ms 121688 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 121644 KB n=5
2 Correct 25 ms 121688 KB n=100
3 Correct 29 ms 121692 KB n=100
4 Correct 36 ms 121440 KB n=100
5 Correct 28 ms 121700 KB n=100
6 Correct 25 ms 121688 KB n=100
7 Correct 25 ms 121688 KB n=100
8 Correct 28 ms 121428 KB n=100
9 Correct 28 ms 121648 KB n=100
10 Correct 31 ms 121688 KB n=100
11 Correct 25 ms 121688 KB n=100
12 Correct 25 ms 121692 KB n=100
13 Correct 26 ms 121692 KB n=100
14 Correct 25 ms 121692 KB n=100
15 Correct 24 ms 121688 KB n=100
16 Correct 24 ms 121688 KB n=100
17 Correct 27 ms 121692 KB n=100
18 Correct 26 ms 121688 KB n=100
19 Correct 25 ms 121528 KB n=100
20 Correct 24 ms 121688 KB n=100
21 Correct 24 ms 121692 KB n=100
22 Correct 25 ms 121692 KB n=100
23 Correct 24 ms 121656 KB n=100
24 Correct 26 ms 121516 KB n=100
25 Correct 25 ms 121464 KB n=100
26 Correct 25 ms 121436 KB n=12
27 Correct 24 ms 121688 KB n=100
28 Correct 25 ms 121692 KB n=500
29 Correct 26 ms 121768 KB n=500
30 Correct 25 ms 121692 KB n=500
31 Correct 26 ms 121688 KB n=500
32 Correct 27 ms 121688 KB n=500
33 Correct 25 ms 121620 KB n=500
34 Correct 24 ms 121688 KB n=500
35 Correct 25 ms 121692 KB n=500
36 Correct 25 ms 121692 KB n=500
37 Correct 27 ms 121788 KB n=500
38 Correct 24 ms 121692 KB n=500
39 Correct 25 ms 121692 KB n=500
40 Correct 24 ms 121684 KB n=500
41 Correct 25 ms 121692 KB n=500
42 Correct 25 ms 121688 KB n=500
43 Correct 25 ms 121888 KB n=500
44 Correct 28 ms 121692 KB n=500
45 Correct 26 ms 121688 KB n=500
46 Correct 25 ms 121688 KB n=500
47 Correct 25 ms 121692 KB n=500
48 Correct 25 ms 121944 KB n=500
49 Correct 25 ms 121740 KB n=500
50 Correct 26 ms 121608 KB n=500
51 Correct 26 ms 121692 KB n=500
52 Correct 27 ms 121688 KB n=500
53 Correct 24 ms 121688 KB n=500
54 Correct 26 ms 121692 KB n=500
55 Correct 24 ms 121692 KB n=278
56 Correct 25 ms 121852 KB n=500
57 Correct 26 ms 121804 KB n=500
58 Correct 26 ms 121948 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 121644 KB n=5
2 Correct 25 ms 121688 KB n=100
3 Correct 29 ms 121692 KB n=100
4 Correct 36 ms 121440 KB n=100
5 Correct 28 ms 121700 KB n=100
6 Correct 25 ms 121688 KB n=100
7 Correct 25 ms 121688 KB n=100
8 Correct 28 ms 121428 KB n=100
9 Correct 28 ms 121648 KB n=100
10 Correct 31 ms 121688 KB n=100
11 Correct 25 ms 121688 KB n=100
12 Correct 25 ms 121692 KB n=100
13 Correct 26 ms 121692 KB n=100
14 Correct 25 ms 121692 KB n=100
15 Correct 24 ms 121688 KB n=100
16 Correct 24 ms 121688 KB n=100
17 Correct 27 ms 121692 KB n=100
18 Correct 26 ms 121688 KB n=100
19 Correct 25 ms 121528 KB n=100
20 Correct 24 ms 121688 KB n=100
21 Correct 24 ms 121692 KB n=100
22 Correct 25 ms 121692 KB n=100
23 Correct 24 ms 121656 KB n=100
24 Correct 26 ms 121516 KB n=100
25 Correct 25 ms 121464 KB n=100
26 Correct 25 ms 121436 KB n=12
27 Correct 24 ms 121688 KB n=100
28 Correct 25 ms 121692 KB n=500
29 Correct 26 ms 121768 KB n=500
30 Correct 25 ms 121692 KB n=500
31 Correct 26 ms 121688 KB n=500
32 Correct 27 ms 121688 KB n=500
33 Correct 25 ms 121620 KB n=500
34 Correct 24 ms 121688 KB n=500
35 Correct 25 ms 121692 KB n=500
36 Correct 25 ms 121692 KB n=500
37 Correct 27 ms 121788 KB n=500
38 Correct 24 ms 121692 KB n=500
39 Correct 25 ms 121692 KB n=500
40 Correct 24 ms 121684 KB n=500
41 Correct 25 ms 121692 KB n=500
42 Correct 25 ms 121688 KB n=500
43 Correct 25 ms 121888 KB n=500
44 Correct 28 ms 121692 KB n=500
45 Correct 26 ms 121688 KB n=500
46 Correct 25 ms 121688 KB n=500
47 Correct 25 ms 121692 KB n=500
48 Correct 25 ms 121944 KB n=500
49 Correct 25 ms 121740 KB n=500
50 Correct 26 ms 121608 KB n=500
51 Correct 26 ms 121692 KB n=500
52 Correct 27 ms 121688 KB n=500
53 Correct 24 ms 121688 KB n=500
54 Correct 26 ms 121692 KB n=500
55 Correct 24 ms 121692 KB n=278
56 Correct 25 ms 121852 KB n=500
57 Correct 26 ms 121804 KB n=500
58 Correct 26 ms 121948 KB n=500
59 Correct 27 ms 123992 KB n=2000
60 Correct 27 ms 124336 KB n=2000
61 Correct 27 ms 124244 KB n=2000
62 Correct 27 ms 124240 KB n=2000
63 Correct 27 ms 123996 KB n=2000
64 Correct 29 ms 124252 KB n=2000
65 Correct 28 ms 123988 KB n=2000
66 Correct 29 ms 124248 KB n=2000
67 Correct 28 ms 123996 KB n=2000
68 Correct 28 ms 124256 KB n=2000
69 Correct 26 ms 123992 KB n=2000
70 Correct 26 ms 123996 KB n=2000
71 Correct 27 ms 124220 KB n=2000
72 Correct 27 ms 123992 KB n=2000
73 Correct 27 ms 124088 KB n=2000
74 Correct 27 ms 123992 KB n=1844
75 Correct 27 ms 123988 KB n=2000
76 Correct 27 ms 123996 KB n=2000
77 Correct 27 ms 123996 KB n=2000
78 Correct 27 ms 123992 KB n=2000
79 Correct 28 ms 123996 KB n=2000
80 Correct 27 ms 124248 KB n=2000
81 Correct 30 ms 124260 KB n=2000
82 Correct 28 ms 124228 KB n=2000
83 Correct 27 ms 124252 KB n=2000
84 Correct 29 ms 124084 KB n=2000
85 Correct 28 ms 124248 KB n=2000
86 Correct 29 ms 124496 KB n=2000
87 Correct 27 ms 124080 KB n=2000
88 Correct 27 ms 124164 KB n=2000
89 Correct 27 ms 124252 KB n=2000
90 Correct 27 ms 124252 KB n=2000
91 Correct 27 ms 124168 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 121644 KB n=5
2 Correct 25 ms 121688 KB n=100
3 Correct 29 ms 121692 KB n=100
4 Correct 36 ms 121440 KB n=100
5 Correct 28 ms 121700 KB n=100
6 Correct 25 ms 121688 KB n=100
7 Correct 25 ms 121688 KB n=100
8 Correct 28 ms 121428 KB n=100
9 Correct 28 ms 121648 KB n=100
10 Correct 31 ms 121688 KB n=100
11 Correct 25 ms 121688 KB n=100
12 Correct 25 ms 121692 KB n=100
13 Correct 26 ms 121692 KB n=100
14 Correct 25 ms 121692 KB n=100
15 Correct 24 ms 121688 KB n=100
16 Correct 24 ms 121688 KB n=100
17 Correct 27 ms 121692 KB n=100
18 Correct 26 ms 121688 KB n=100
19 Correct 25 ms 121528 KB n=100
20 Correct 24 ms 121688 KB n=100
21 Correct 24 ms 121692 KB n=100
22 Correct 25 ms 121692 KB n=100
23 Correct 24 ms 121656 KB n=100
24 Correct 26 ms 121516 KB n=100
25 Correct 25 ms 121464 KB n=100
26 Correct 25 ms 121436 KB n=12
27 Correct 24 ms 121688 KB n=100
28 Correct 25 ms 121692 KB n=500
29 Correct 26 ms 121768 KB n=500
30 Correct 25 ms 121692 KB n=500
31 Correct 26 ms 121688 KB n=500
32 Correct 27 ms 121688 KB n=500
33 Correct 25 ms 121620 KB n=500
34 Correct 24 ms 121688 KB n=500
35 Correct 25 ms 121692 KB n=500
36 Correct 25 ms 121692 KB n=500
37 Correct 27 ms 121788 KB n=500
38 Correct 24 ms 121692 KB n=500
39 Correct 25 ms 121692 KB n=500
40 Correct 24 ms 121684 KB n=500
41 Correct 25 ms 121692 KB n=500
42 Correct 25 ms 121688 KB n=500
43 Correct 25 ms 121888 KB n=500
44 Correct 28 ms 121692 KB n=500
45 Correct 26 ms 121688 KB n=500
46 Correct 25 ms 121688 KB n=500
47 Correct 25 ms 121692 KB n=500
48 Correct 25 ms 121944 KB n=500
49 Correct 25 ms 121740 KB n=500
50 Correct 26 ms 121608 KB n=500
51 Correct 26 ms 121692 KB n=500
52 Correct 27 ms 121688 KB n=500
53 Correct 24 ms 121688 KB n=500
54 Correct 26 ms 121692 KB n=500
55 Correct 24 ms 121692 KB n=278
56 Correct 25 ms 121852 KB n=500
57 Correct 26 ms 121804 KB n=500
58 Correct 26 ms 121948 KB n=500
59 Correct 27 ms 123992 KB n=2000
60 Correct 27 ms 124336 KB n=2000
61 Correct 27 ms 124244 KB n=2000
62 Correct 27 ms 124240 KB n=2000
63 Correct 27 ms 123996 KB n=2000
64 Correct 29 ms 124252 KB n=2000
65 Correct 28 ms 123988 KB n=2000
66 Correct 29 ms 124248 KB n=2000
67 Correct 28 ms 123996 KB n=2000
68 Correct 28 ms 124256 KB n=2000
69 Correct 26 ms 123992 KB n=2000
70 Correct 26 ms 123996 KB n=2000
71 Correct 27 ms 124220 KB n=2000
72 Correct 27 ms 123992 KB n=2000
73 Correct 27 ms 124088 KB n=2000
74 Correct 27 ms 123992 KB n=1844
75 Correct 27 ms 123988 KB n=2000
76 Correct 27 ms 123996 KB n=2000
77 Correct 27 ms 123996 KB n=2000
78 Correct 27 ms 123992 KB n=2000
79 Correct 28 ms 123996 KB n=2000
80 Correct 27 ms 124248 KB n=2000
81 Correct 30 ms 124260 KB n=2000
82 Correct 28 ms 124228 KB n=2000
83 Correct 27 ms 124252 KB n=2000
84 Correct 29 ms 124084 KB n=2000
85 Correct 28 ms 124248 KB n=2000
86 Correct 29 ms 124496 KB n=2000
87 Correct 27 ms 124080 KB n=2000
88 Correct 27 ms 124164 KB n=2000
89 Correct 27 ms 124252 KB n=2000
90 Correct 27 ms 124252 KB n=2000
91 Correct 27 ms 124168 KB n=2000
92 Correct 589 ms 190568 KB n=200000
93 Correct 858 ms 197204 KB n=200000
94 Correct 894 ms 200856 KB n=200000
95 Correct 563 ms 190144 KB n=200000
96 Correct 578 ms 190176 KB n=200000
97 Correct 896 ms 195716 KB n=200000
98 Correct 562 ms 190172 KB n=200000
99 Correct 663 ms 190652 KB n=200000
100 Correct 584 ms 190236 KB n=200000
101 Correct 863 ms 202228 KB n=200000
102 Correct 321 ms 191784 KB n=200000
103 Correct 344 ms 191816 KB n=200000
104 Correct 333 ms 192020 KB n=200000
105 Correct 336 ms 192300 KB n=200000
106 Correct 349 ms 192156 KB n=200000
107 Correct 344 ms 192084 KB n=200000
108 Correct 614 ms 190544 KB n=200000
109 Correct 641 ms 190548 KB n=200000
110 Correct 636 ms 190496 KB n=200000
111 Correct 552 ms 189888 KB n=200000
112 Correct 892 ms 201280 KB n=200000
113 Correct 896 ms 195648 KB n=200000
114 Correct 565 ms 189888 KB n=200000
115 Correct 885 ms 193196 KB n=200000
116 Correct 561 ms 190656 KB n=200000
117 Correct 829 ms 201624 KB n=200000
118 Correct 903 ms 194444 KB n=200000
119 Correct 544 ms 190432 KB n=200000
120 Correct 823 ms 201324 KB n=200000
121 Correct 847 ms 201368 KB n=200000
122 Correct 858 ms 201552 KB n=200000
123 Correct 332 ms 192072 KB n=200000
124 Correct 167 ms 138820 KB n=25264