Submission #702979

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
702979	2023-02-25 11:51:44	piOOE	Jail (JOI22_jail)	C++17	100 / 100	1118 ms	101756 KiB

jail

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
class HLD {
public:
    vector<int> par, siz, head, tin, tout, ord, depth;
    int dfs1(int i, vector<vector<int>> &g) {
        for (int &t: g[i]) {
            if (t != par[i]) {
                depth[t] = depth[i] + 1;
                par[t] = i;
                siz[i] += dfs1(t, g);
                if (siz[t] > siz[g[i][0]] || g[i][0] == par[i]) swap(t, g[i][0]);
            }
        }
        return siz[i];
    }
    void dfs2(int i, int &T, const vector<vector<int>> &g) {
        tin[i] = T++;
        for (int t: g[i]) {
            if (t != par[i]) {
                head[t] = (T == tin[i] + 1 ? head[i] : t);
                dfs2(t, T, g);
            }
        }
        tout[i] = T;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

jail.cpp: In constructor 'HLD::HLD(std::vector<std::vector<int> >, int)':
jail.cpp:8:44: warning: 'HLD::ord' will be initialized after [-Wreorder]
    8 |     vector<int> par, siz, head, tin, tout, ord, depth;
      |                                            ^~~
jail.cpp:8:38: warning:   'std::vector<int> HLD::tout' [-Wreorder]
    8 |     vector<int> par, siz, head, tin, tout, ord, depth;
      |                                      ^~~~
jail.cpp:33:5: warning:   when initialized here [-Wreorder]
   33 |     HLD(vector<vector<int>> g, int r = 0)
      |     ^~~
jail.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int i = 0; i < g.size(); ++i) ord[tin[i]] = i;
      |                         ~~^~~~~~~~~~
jail.cpp: In function 'void init(int)':
jail.cpp:84:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   84 |     sz = 1 << __lg(n) + !!(n & (n - 1));
      |               ~~~~~~~~^~~~~~~~~~~~~~~~~
jail.cpp: In instantiation of 'solve()::<lambda(auto:23, int, int, int, int, int)> [with auto:23 = solve()::<lambda(auto:23, int, int, int, int, int)>]':
jail.cpp:158:42:   required from here
jail.cpp:144:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |             int mid = lx + rx >> 1;
      |                       ~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23