oj.uz

Submission #854683

# Submission time Handle Problem Language Result Execution time Memory
854683 2023-09-28T14:01:21 Z hariaakas646 Birthday gift (IZhO18_treearray) C++17
100 / 100
 1052 ms 91776 KB 
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}

vvi graph;
vi depth;
vvi lift;

void dfs(int x, int p, int d) {
    lift[x][0] = p;
    depth[x] = d;

    for(auto e : graph[x]) {
        if(e != p) {
            dfs(e, x, d+1);
        }
    }
}

int binlift(int x, int c) {
    frange(i, 20) {
        if(c & (1<<i)) {
            x = lift[x][i];
        }
    }
    return x;
}

int lca(int u, int v) {
    if(depth[u] > depth[v]) swap(u, v);

    v = binlift(v, depth[v] - depth[u]);

    if(v == u) return u;

    for(int i=19; i>=0; i--) {
        int ut = lift[u][i];
        int vt = lift[v][i];
        if(ut != vt) {
            u = ut;
            v= vt;
        }
    }
    return lift[u][0];
}

int main() {
    // usaco();
    int n, m, q;
    scd(n);
    scd(m);
    scd(q);
    graph = vvi(n+1);

    frange(i, n-1) {
        int a, b;
        scd(a);
        scd(b);
        graph[a].pb(b);
        graph[b].pb(a);
    }

    depth = vi(n+1);
    lift = vvi(n+1, vi(20));

    dfs(1, 0, 0);

    forr(i, 1, 20) {
        forr(j, 1, n+1) {
            lift[j][i] = lift[lift[j][i-1]][i-1];
        }
    }

    vi vec(m+1);

    vector<seti> one(n+1), two(n+1);

    forr(i, 1, m+1) {
        int a;
        scd(a);
        vec[i] = a;
        one[a].insert(i);
        if(i > 1) {
            int l = lca(vec[i], vec[i-1]);
            two[l].insert(i-1);
        }
    }

    frange(_, q) {
        int t;
        scd(t);
        if(t == 1) {
            int pos, v;
            scd(pos);
            scd(v);
            // printf("%d %d %d\n", t, pos, v);
            one[vec[pos]].erase(pos);
            one[v].insert(pos);

            if(pos > 1) {
                int l = lca(vec[pos], vec[pos-1]);
                two[l].erase(pos-1);
                l = lca(v, vec[pos-1]);
                two[l].insert(pos-1);
            }
            if(pos < m) {
                int l = lca(vec[pos], vec[pos+1]);
                two[l].erase(pos);
                l = lca(v, vec[pos+1]);
                two[l].insert(pos);
            }
            vec[pos] = v;
        }
        else {
            int l, r, v;
            scd(l);
            scd(r);
            scd(v);
            auto it = one[v].lower_bound(l);
            if(it != one[v].end()) {
                if(*it <= r) {
                    printf("%d %d\n", *it, *it);
                    continue;
                }
            }
            auto it2 = two[v].lower_bound(l);
            if(it2 != two[v].end()) {
                if(*it2 < r) {
                    printf("%d %d\n", *it2, (*it2)+1);
                    continue;
                }
            }
            printf("-1 -1\n");
        }
    }

}

Compilation message

treearray.cpp: In function 'void usaco()':
treearray.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp: In function 'int main()':
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:78:5: note: in expansion of macro 'scd'
   78 |     scd(n);
      |     ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:79:5: note: in expansion of macro 'scd'
   79 |     scd(m);
      |     ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:80:5: note: in expansion of macro 'scd'
   80 |     scd(q);
      |     ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:85:9: note: in expansion of macro 'scd'
   85 |         scd(a);
      |         ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:86:9: note: in expansion of macro 'scd'
   86 |         scd(b);
      |         ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:108:9: note: in expansion of macro 'scd'
  108 |         scd(a);
      |         ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:119:9: note: in expansion of macro 'scd'
  119 |         scd(t);
      |         ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:122:13: note: in expansion of macro 'scd'
  122 |             scd(pos);
      |             ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:123:13: note: in expansion of macro 'scd'
  123 |             scd(v);
      |             ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:144:13: note: in expansion of macro 'scd'
  144 |             scd(l);
      |             ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:145:13: note: in expansion of macro 'scd'
  145 |             scd(r);
      |             ^~~
treearray.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
treearray.cpp:146:13: note: in expansion of macro 'scd'
  146 |             scd(v);
      |             ^~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n=5
2 Correct 1 ms 348 KB n=100
3 Correct 0 ms 348 KB n=100
4 Correct 0 ms 348 KB n=100
5 Correct 0 ms 344 KB n=100
6 Correct 0 ms 348 KB n=100
7 Correct 0 ms 348 KB n=100
8 Correct 0 ms 348 KB n=100
9 Correct 0 ms 348 KB n=100
10 Correct 1 ms 344 KB n=100
11 Correct 1 ms 348 KB n=100
12 Correct 0 ms 348 KB n=100
13 Correct 1 ms 348 KB n=100
14 Correct 0 ms 348 KB n=100
15 Correct 1 ms 348 KB n=100
16 Correct 0 ms 348 KB n=100
17 Correct 1 ms 348 KB n=100
18 Correct 0 ms 348 KB n=100
19 Correct 0 ms 348 KB n=100
20 Correct 1 ms 348 KB n=100
21 Correct 1 ms 348 KB n=100
22 Correct 1 ms 348 KB n=100
23 Correct 1 ms 348 KB n=100
24 Correct 1 ms 348 KB n=100
25 Correct 0 ms 348 KB n=100
26 Correct 0 ms 348 KB n=12
27 Correct 0 ms 348 KB n=100
28 Correct 1 ms 604 KB n=500
29 Correct 1 ms 604 KB n=500
30 Correct 1 ms 604 KB n=500
31 Correct 1 ms 604 KB n=500
32 Correct 1 ms 604 KB n=500
33 Correct 1 ms 600 KB n=500
34 Correct 1 ms 600 KB n=500
35 Correct 1 ms 604 KB n=500
36 Correct 1 ms 600 KB n=500
37 Correct 1 ms 604 KB n=500
38 Correct 1 ms 604 KB n=500
39 Correct 1 ms 604 KB n=500
40 Correct 1 ms 604 KB n=500
41 Correct 1 ms 604 KB n=500
42 Correct 1 ms 604 KB n=500
43 Correct 1 ms 600 KB n=500
44 Correct 1 ms 604 KB n=500
45 Correct 1 ms 604 KB n=500
46 Correct 1 ms 604 KB n=500
47 Correct 1 ms 600 KB n=500
48 Correct 1 ms 600 KB n=500
49 Correct 1 ms 604 KB n=500
50 Correct 1 ms 604 KB n=500
51 Correct 1 ms 856 KB n=500
52 Correct 1 ms 600 KB n=500
53 Correct 1 ms 600 KB n=500
54 Correct 1 ms 604 KB n=500
55 Correct 1 ms 348 KB n=278
56 Correct 1 ms 600 KB n=500
57 Correct 1 ms 604 KB n=500
58 Correct 1 ms 600 KB n=500
59 Correct 3 ms 1116 KB n=2000
60 Correct 3 ms 1116 KB n=2000
61 Correct 3 ms 1116 KB n=2000
62 Correct 3 ms 1112 KB n=2000
63 Correct 3 ms 1116 KB n=2000
64 Correct 4 ms 1116 KB n=2000
65 Correct 3 ms 1116 KB n=2000
66 Correct 3 ms 1112 KB n=2000
67 Correct 3 ms 1112 KB n=2000
68 Correct 3 ms 1116 KB n=2000
69 Correct 3 ms 1112 KB n=2000
70 Correct 2 ms 1116 KB n=2000
71 Correct 3 ms 1116 KB n=2000
72 Correct 2 ms 1116 KB n=2000
73 Correct 3 ms 1116 KB n=2000
74 Correct 3 ms 1116 KB n=1844
75 Correct 2 ms 1116 KB n=2000
76 Correct 3 ms 1116 KB n=2000
77 Correct 3 ms 1116 KB n=2000
78 Correct 4 ms 1312 KB n=2000
79 Correct 3 ms 1116 KB n=2000
80 Correct 3 ms 1116 KB n=2000
81 Correct 3 ms 1116 KB n=2000
82 Correct 3 ms 1112 KB n=2000
83 Correct 3 ms 1112 KB n=2000
84 Correct 3 ms 1180 KB n=2000
85 Correct 3 ms 1116 KB n=2000
86 Correct 4 ms 1116 KB n=2000
87 Correct 4 ms 1116 KB n=2000
88 Correct 3 ms 1116 KB n=2000
89 Correct 3 ms 1116 KB n=2000
90 Correct 3 ms 1116 KB n=2000
91 Correct 2 ms 1116 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n=5
2 Correct 1 ms 348 KB n=100
3 Correct 0 ms 348 KB n=100
4 Correct 0 ms 348 KB n=100
5 Correct 0 ms 344 KB n=100
6 Correct 0 ms 348 KB n=100
7 Correct 0 ms 348 KB n=100
8 Correct 0 ms 348 KB n=100
9 Correct 0 ms 348 KB n=100
10 Correct 1 ms 344 KB n=100
11 Correct 1 ms 348 KB n=100
12 Correct 0 ms 348 KB n=100
13 Correct 1 ms 348 KB n=100
14 Correct 0 ms 348 KB n=100
15 Correct 1 ms 348 KB n=100
16 Correct 0 ms 348 KB n=100
17 Correct 1 ms 348 KB n=100
18 Correct 0 ms 348 KB n=100
19 Correct 0 ms 348 KB n=100
20 Correct 1 ms 348 KB n=100
21 Correct 1 ms 348 KB n=100
22 Correct 1 ms 348 KB n=100
23 Correct 1 ms 348 KB n=100
24 Correct 1 ms 348 KB n=100
25 Correct 0 ms 348 KB n=100
26 Correct 0 ms 348 KB n=12
27 Correct 0 ms 348 KB n=100
28 Correct 1 ms 604 KB n=500
29 Correct 1 ms 604 KB n=500
30 Correct 1 ms 604 KB n=500
31 Correct 1 ms 604 KB n=500
32 Correct 1 ms 604 KB n=500
33 Correct 1 ms 600 KB n=500
34 Correct 1 ms 600 KB n=500
35 Correct 1 ms 604 KB n=500
36 Correct 1 ms 600 KB n=500
37 Correct 1 ms 604 KB n=500
38 Correct 1 ms 604 KB n=500
39 Correct 1 ms 604 KB n=500
40 Correct 1 ms 604 KB n=500
41 Correct 1 ms 604 KB n=500
42 Correct 1 ms 604 KB n=500
43 Correct 1 ms 600 KB n=500
44 Correct 1 ms 604 KB n=500
45 Correct 1 ms 604 KB n=500
46 Correct 1 ms 604 KB n=500
47 Correct 1 ms 600 KB n=500
48 Correct 1 ms 600 KB n=500
49 Correct 1 ms 604 KB n=500
50 Correct 1 ms 604 KB n=500
51 Correct 1 ms 856 KB n=500
52 Correct 1 ms 600 KB n=500
53 Correct 1 ms 600 KB n=500
54 Correct 1 ms 604 KB n=500
55 Correct 1 ms 348 KB n=278
56 Correct 1 ms 600 KB n=500
57 Correct 1 ms 604 KB n=500
58 Correct 1 ms 600 KB n=500
59 Correct 3 ms 1116 KB n=2000
60 Correct 3 ms 1116 KB n=2000
61 Correct 3 ms 1116 KB n=2000
62 Correct 3 ms 1112 KB n=2000
63 Correct 3 ms 1116 KB n=2000
64 Correct 4 ms 1116 KB n=2000
65 Correct 3 ms 1116 KB n=2000
66 Correct 3 ms 1112 KB n=2000
67 Correct 3 ms 1112 KB n=2000
68 Correct 3 ms 1116 KB n=2000
69 Correct 3 ms 1112 KB n=2000
70 Correct 2 ms 1116 KB n=2000
71 Correct 3 ms 1116 KB n=2000
72 Correct 2 ms 1116 KB n=2000
73 Correct 3 ms 1116 KB n=2000
74 Correct 3 ms 1116 KB n=1844
75 Correct 2 ms 1116 KB n=2000
76 Correct 3 ms 1116 KB n=2000
77 Correct 3 ms 1116 KB n=2000
78 Correct 4 ms 1312 KB n=2000
79 Correct 3 ms 1116 KB n=2000
80 Correct 3 ms 1116 KB n=2000
81 Correct 3 ms 1116 KB n=2000
82 Correct 3 ms 1112 KB n=2000
83 Correct 3 ms 1112 KB n=2000
84 Correct 3 ms 1180 KB n=2000
85 Correct 3 ms 1116 KB n=2000
86 Correct 4 ms 1116 KB n=2000
87 Correct 4 ms 1116 KB n=2000
88 Correct 3 ms 1116 KB n=2000
89 Correct 3 ms 1116 KB n=2000
90 Correct 3 ms 1116 KB n=2000
91 Correct 2 ms 1116 KB n=2000
92 Correct 679 ms 78776 KB n=200000
93 Correct 992 ms 87636 KB n=200000
94 Correct 953 ms 90596 KB n=200000
95 Correct 669 ms 82456 KB n=200000
96 Correct 634 ms 82352 KB n=200000
97 Correct 1030 ms 86408 KB n=200000
98 Correct 667 ms 82304 KB n=200000
99 Correct 845 ms 82516 KB n=200000
100 Correct 614 ms 82376 KB n=200000
101 Correct 968 ms 91776 KB n=200000
102 Correct 389 ms 83588 KB n=200000
103 Correct 383 ms 83476 KB n=200000
104 Correct 393 ms 83284 KB n=200000
105 Correct 411 ms 83800 KB n=200000
106 Correct 430 ms 83792 KB n=200000
107 Correct 384 ms 83792 KB n=200000
108 Correct 725 ms 82312 KB n=200000
109 Correct 750 ms 82588 KB n=200000
110 Correct 763 ms 82568 KB n=200000
111 Correct 612 ms 81752 KB n=200000
112 Correct 954 ms 90968 KB n=200000
113 Correct 946 ms 86652 KB n=200000
114 Correct 603 ms 81860 KB n=200000
115 Correct 956 ms 84508 KB n=200000
116 Correct 661 ms 82376 KB n=200000
117 Correct 974 ms 91344 KB n=200000
118 Correct 1052 ms 85508 KB n=200000
119 Correct 658 ms 82532 KB n=200000
120 Correct 914 ms 90956 KB n=200000
121 Correct 850 ms 90928 KB n=200000
122 Correct 932 ms 91240 KB n=200000
123 Correct 389 ms 83732 KB n=200000
124 Correct 133 ms 19280 KB n=25264