Submission #838837

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
838837	2023-08-27T21:25:05 Z	Joshua_Andersson	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	368 ms	106652 KB

catinatree

#undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

#define enablell 1

typedef long long ll;
typedef unsigned long long ull;
#if enablell
#define int ll
#define inf int(1e18)
#else
const int inf = int(2e9);
#endif
typedef vector<ull> vull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef pair<int, int> p2;
typedef vector<p2> vp2;
typedef vector<vp2> vvp2;
typedef vector<vvp2> vvvp2;
typedef tuple<int, int, int> p3;
typedef vector<p3> vp3;
typedef vector<vp3> vvp3;
typedef vector<vvp3> vvvp3;
typedef tuple<int, int, int, int> p4;
typedef vector<p4> vp4;

#define _LOCAL _MSC_VER > 0
#if _LOCAL

#define assert(x) debassert(x)
#define popcount(x) __popcnt(x)
uint32_t clz(uint32_t x) { return _lzcnt_u32(x); }
uint32_t ctz(uint32_t x) { return _tzcnt_u32(x); }
#define bswap64(x) _byteswap_uint64(x)
#else

#define popcount(x) __builtin_popcountll(x)
uint32_t clz(uint32_t x) { return __builtin_clz(x); }
uint32_t ctz(uint32_t x) { return __builtin_ctzll(x); }
#define bswap64(x) __builtin_bswap64(x)

#if 0
namespace pbds
{
    using namespace __gnu_pbds;

    template<typename T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    template<typename T, typename U> using indexed_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

    struct chash { // large odd number for C
        const uint64_t C = ll(4e18 * acos(0)) | 71;
        ll operator()(ll x) const { return __builtin_bswap64(x * C); }
    };
    template<typename T, typename U> using fast_map = __gnu_pbds::gp_hash_table<T, U, chash>;
    template<typename T> using fast_set = __gnu_pbds::gp_hash_table<T, null_type, chash>;
    template<typename T, typename H> using fast_set_h = __gnu_pbds::gp_hash_table<T, null_type, H>;
}
using namespace pbds;
#endif
#endif

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
#define FAST_INPUT 0
#if FAST_INPUT && !_LOCAL
#define gc() getchar_unlocked()
inline void read(int& v) { v = 0; int sign = 1; char c = gc(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = gc()) && c != ' ' && c != '\n') { if (c == EOF) { v = -1; return; } v *= 10; v += c - '0'; } v *= sign; }
inline void read(int& u, int& v) { read(u); read(v); }
inline void read(int& u, int& v, int& k) { read(u); read(v); read(k); }
//inline void read(int& v) { char c; while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } }
inline void read(string& s) { char c; while ((c = gc()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } }
inline void readline(string& s) { char c; while ((c = gc()) != EOF && c != '\n') { s.push_back(c); } }
#else
template <typename T> inline void read(T& a) { cin >> a; }
template <typename T> inline void read(T& a, T& b) { cin >> a >> b; }
template <typename T> inline void read(T& a, T& b, T& c) { cin >> a >> b >> c; }
#endif
#define quit cout << endl; _Exit(0);
#define dread(type, a) type a; read(a)
#define dread2(type, a, b) dread(type, a); dread(type, b)
#define dread3(type, a, b, c) dread2(type, a, b); dread(type, c)
#define dread4(type, a, b, c, d) dread3(type, a, b, c); dread(type, d)
#define dread5(type, a, b, c, d, e) dread4(type, a, b, c, d); dread(type, e)
#define readvector(type, name, size) vector<type> name(size); rep(i,size) {dread(type,temp); name[i]=temp;}
#ifdef _DEBUG
#define noop cout << "";
#define deb __debugbreak();
#define debassert(expr) if(!(expr)) deb;
#define debif(expr) if(expr) deb;
void print(const string& s) { cout << s << "\n"; }
#else
#define noop ;
#define deb ;
#define debif(expr) ;
#define debassert(expr) ;
void print(const string& s) {  }
#endif

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define per(i, high) for (int i = high-1; i >= 0; i--)

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define setcontains(set, x) (set.find(x) != set.end())
#define sz(container) ((int)container.size())
#define mp(a,b) (make_pair(a,b))

#define ceildiv(x,y) ((x + y - 1) / y)

template <typename T, typename U> inline void operator+=(pair<T, U>& l, const pair<T, U>& r) { l = { l.first + r.first,l.second + r.second }; }
template <typename T, typename U> inline pair<T, U> operator+(const pair<T, U> l, const pair<T, U> r) { return { l.first + r.first, l.second + r.second }; }
template <typename T, typename U> inline pair<T, U> operator-(const pair<T, U> l, const pair<T, U> r) { return { l.first - r.first, l.second - r.second }; }
template <typename T, typename U> inline pair<T, U> operator*(const pair<T, U> l, const int m) { return { l.first * m, l.second * m }; }
template <typename Out> inline void split(const string& s, char delim, Out result) { istringstream iss(s); string item; while (getline(iss, item, delim)) { *result++ = item; } }
inline vector<string> split(const string& s, char delim) { vector<string> elems; split(s, delim, back_inserter(elems)); return elems; }
vector<string> split(string s, string d) { size_t k = 0, n, e = d.length(); string t; vector<string> r; while ((n = s.find(d, k)) != string::npos) { t = s.substr(k, n - k); k = n + e; r.push_back(t); } r.push_back(s.substr(k)); return r; }
ll binpow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll m) { a %= m; long long res = 1; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } // For a < 2^31

#if 1
auto Start = chrono::high_resolution_clock::now();
void resettimer() { Start = chrono::high_resolution_clock::now(); }
int elapsedmillis() { return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count(); }
random_device rd;
mt19937 rng(rd());
template<typename T, typename U> inline int randint(T lo, U hi) { return uniform_int_distribution<int>((int)lo, (int)hi)(rng); } // [lo,hi]
template<typename T> inline T randel(vector<T>& v) { return v[uniform_int_distribution<int>(int(0), int(v.size()) - int(1))(rng)]; } // [lo,hi]
#endif
const ll mod = 1e9 + 7;
vp2 dirs = { {0,1},{0,-1},{1,0},{-1,0} };

const int hi = int(2e5 + 10);
struct LCA
{
    LCA() {}
    LCA(vvi& edges)
    {
        dfs(0, 0, 0, edges);
    }

    int up[19][hi];
    int depth[hi];
    int tin[hi];
    int tout[hi];
    int timer = 0;
    void dfs(int u, int p, int d, vvi& edges)
    {
        up[0][u] = p;
        repp(d, 1, 19) up[d][u] = up[d-1][up[d - 1][u]];

        depth[u] = d;
        tin[u] = timer++;

        repe(e, edges[u])
        {
            if (e == p) continue;
            dfs(e, u, d + 1, edges);
        }
        tout[u] = timer++;
    }

    bool isancestor(int a, int b)
    {
        return tin[a] <= tin[b] && tout[a] >= tout[b];
    }

    int lca(int a, int b)
    {
        if (isancestor(a, b)) return a;
        if (isancestor(b, a)) return b;

        per(d, 19)
        {
            if (!isancestor(up[d][a], b)) a = up[d][a];
        }

        return up[0][a];
    }

    int dist(int a, int b)
    {
        int c = lca(a, b);
        return depth[a] + depth[b] - 2 * depth[c];
    }
};

struct Centroid
{
    int n;
    vvi edges;
    vb vis;
    vi par;
    vi size;

    Centroid() {}
    Centroid(vvi& edges) : edges(edges), n(edges.size()), vis(n),par(n),size(n)
    {
        init_centroid(0, -1);
    }

    int find_centroid(int u, int p, int n)
    {
        repe(e, edges[u])
        {
            if (e == p) continue;
            if (!vis[e] && size[e] > n / 2) return find_centroid(e, u, n);
        }
        return u;
    }

    int find_size(int u, int p)
    {
        if (vis[u]) return 0;
        size[u] = 1;

        repe(e, edges[u])
        {
            if (e == p) continue;
            size[u] += find_size(e, u);
        }
        return size[u];
    }

    void init_centroid(int u, int p)
    {
        find_size(u, u);

        int c = find_centroid(u, u, size[u]);
        vis[c] = 1;
        par[c] = p;

        repe(e, edges[c])
        {
            if (!vis[e]) init_centroid(e, c);
        }
    }
};

Centroid centroid;
LCA lca;
vi best;
void update(int u)
{
    int v = u;
    do 
    {
        best[v] = min(best[v], lca.dist(v, u));
        v = centroid.par[v];
    } while (v != -1);
}

int query(int u)
{
    int ans = inf;

    int v = u;
    do
    {
        ans = min(ans, best[v] + lca.dist(v, u));
        v = centroid.par[v];
    } while (v!=-1);

    return ans;
}

int32_t main()
{
    fast();
#if 1 && _LOCAL
    ifstream instream("C:\\users\\matis\\Desktop\\comp_prog\\x64\\debug\\in.txt");
    cin.rdbuf(instream.rdbuf());
#endif

    dread2(int, n, d);
    best.resize(n, inf);
    vvi edges(n);
    rep(i,n-1)
    {
        dread(int, p);
        edges[i+1].push_back(p);
        edges[p].push_back(i+1);
    }
    lca = LCA(edges);
    centroid = Centroid(edges);

    priority_queue<p2> pq;
    rep(i, n)
    {
        pq.emplace(lca.depth[i], i);
    }

    int ans = 0;
    while (pq.size())
    {
        int _, u;
        tie(_, u) = pq.top(); pq.pop();
        //cerr << query(u) << " " << u << "\n";
        if (query(u) < d) continue;
        update(u);
        ans++;
    }
    cout << ans;

    quit;
}

Compilation message

catinatree.cpp: In constructor 'Centroid::Centroid(vvi&)':
catinatree.cpp:207:9: warning: 'Centroid::edges' will be initialized after [-Wreorder]
  207 |     vvi edges;
      |         ^~~~~
catinatree.cpp:206:9: warning:   'll Centroid::n' [-Wreorder]
  206 |     int n;
      |         ^
catinatree.cpp:213:5: warning:   when initialized here [-Wreorder]
  213 |     Centroid(vvi& edges) : edges(edges), n(edges.size()), vis(n),par(n),size(n)
      |     ^~~~~~~~

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	69164 KB	Output is correct
2	Correct	26 ms	69172 KB	Output is correct
3	Correct	27 ms	69112 KB	Output is correct
4	Correct	26 ms	69148 KB	Output is correct
5	Correct	25 ms	69112 KB	Output is correct
6	Correct	26 ms	69092 KB	Output is correct
7	Correct	26 ms	69204 KB	Output is correct
8	Correct	26 ms	69180 KB	Output is correct
9	Correct	26 ms	69088 KB	Output is correct
10	Correct	27 ms	69200 KB	Output is correct
11	Correct	27 ms	69072 KB	Output is correct
12	Correct	27 ms	69096 KB	Output is correct
13	Correct	27 ms	69080 KB	Output is correct
14	Correct	26 ms	69112 KB	Output is correct
15	Correct	26 ms	69204 KB	Output is correct
16	Correct	26 ms	69156 KB	Output is correct
17	Correct	26 ms	69204 KB	Output is correct
18	Correct	26 ms	69124 KB	Output is correct
19	Correct	27 ms	69156 KB	Output is correct
20	Correct	27 ms	69096 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	69164 KB	Output is correct
2	Correct	26 ms	69172 KB	Output is correct
3	Correct	27 ms	69112 KB	Output is correct
4	Correct	26 ms	69148 KB	Output is correct
5	Correct	25 ms	69112 KB	Output is correct
6	Correct	26 ms	69092 KB	Output is correct
7	Correct	26 ms	69204 KB	Output is correct
8	Correct	26 ms	69180 KB	Output is correct
9	Correct	26 ms	69088 KB	Output is correct
10	Correct	27 ms	69200 KB	Output is correct
11	Correct	27 ms	69072 KB	Output is correct
12	Correct	27 ms	69096 KB	Output is correct
13	Correct	27 ms	69080 KB	Output is correct
14	Correct	26 ms	69112 KB	Output is correct
15	Correct	26 ms	69204 KB	Output is correct
16	Correct	26 ms	69156 KB	Output is correct
17	Correct	26 ms	69204 KB	Output is correct
18	Correct	26 ms	69124 KB	Output is correct
19	Correct	27 ms	69156 KB	Output is correct
20	Correct	27 ms	69096 KB	Output is correct
21	Correct	27 ms	69444 KB	Output is correct
22	Correct	26 ms	69204 KB	Output is correct
23	Correct	28 ms	69184 KB	Output is correct
24	Correct	26 ms	69296 KB	Output is correct
25	Correct	27 ms	69264 KB	Output is correct
26	Correct	27 ms	69368 KB	Output is correct
27	Correct	26 ms	69364 KB	Output is correct
28	Correct	28 ms	69436 KB	Output is correct
29	Correct	28 ms	69460 KB	Output is correct
30	Correct	27 ms	69484 KB	Output is correct
31	Correct	26 ms	69456 KB	Output is correct
32	Correct	27 ms	69444 KB	Output is correct
33	Correct	27 ms	69452 KB	Output is correct
34	Correct	26 ms	69404 KB	Output is correct
35	Correct	27 ms	69396 KB	Output is correct
36	Correct	27 ms	69400 KB	Output is correct
37	Correct	28 ms	69452 KB	Output is correct
38	Correct	27 ms	69460 KB	Output is correct
39	Correct	27 ms	69400 KB	Output is correct
40	Correct	28 ms	69520 KB	Output is correct

Subtask #3

49.0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	69164 KB	Output is correct
2	Correct	26 ms	69172 KB	Output is correct
3	Correct	27 ms	69112 KB	Output is correct
4	Correct	26 ms	69148 KB	Output is correct
5	Correct	25 ms	69112 KB	Output is correct
6	Correct	26 ms	69092 KB	Output is correct
7	Correct	26 ms	69204 KB	Output is correct
8	Correct	26 ms	69180 KB	Output is correct
9	Correct	26 ms	69088 KB	Output is correct
10	Correct	27 ms	69200 KB	Output is correct
11	Correct	27 ms	69072 KB	Output is correct
12	Correct	27 ms	69096 KB	Output is correct
13	Correct	27 ms	69080 KB	Output is correct
14	Correct	26 ms	69112 KB	Output is correct
15	Correct	26 ms	69204 KB	Output is correct
16	Correct	26 ms	69156 KB	Output is correct
17	Correct	26 ms	69204 KB	Output is correct
18	Correct	26 ms	69124 KB	Output is correct
19	Correct	27 ms	69156 KB	Output is correct
20	Correct	27 ms	69096 KB	Output is correct
21	Correct	27 ms	69444 KB	Output is correct
22	Correct	26 ms	69204 KB	Output is correct
23	Correct	28 ms	69184 KB	Output is correct
24	Correct	26 ms	69296 KB	Output is correct
25	Correct	27 ms	69264 KB	Output is correct
26	Correct	27 ms	69368 KB	Output is correct
27	Correct	26 ms	69364 KB	Output is correct
28	Correct	28 ms	69436 KB	Output is correct
29	Correct	28 ms	69460 KB	Output is correct
30	Correct	27 ms	69484 KB	Output is correct
31	Correct	26 ms	69456 KB	Output is correct
32	Correct	27 ms	69444 KB	Output is correct
33	Correct	27 ms	69452 KB	Output is correct
34	Correct	26 ms	69404 KB	Output is correct
35	Correct	27 ms	69396 KB	Output is correct
36	Correct	27 ms	69400 KB	Output is correct
37	Correct	28 ms	69452 KB	Output is correct
38	Correct	27 ms	69460 KB	Output is correct
39	Correct	27 ms	69400 KB	Output is correct
40	Correct	28 ms	69520 KB	Output is correct
41	Correct	124 ms	99952 KB	Output is correct
42	Correct	163 ms	85544 KB	Output is correct
43	Correct	152 ms	85588 KB	Output is correct
44	Correct	155 ms	85480 KB	Output is correct
45	Correct	159 ms	85576 KB	Output is correct
46	Correct	368 ms	101744 KB	Output is correct
47	Correct	351 ms	101760 KB	Output is correct
48	Correct	364 ms	101812 KB	Output is correct
49	Correct	356 ms	101828 KB	Output is correct
50	Correct	98 ms	86528 KB	Output is correct
51	Correct	99 ms	86512 KB	Output is correct
52	Correct	93 ms	86464 KB	Output is correct
53	Correct	193 ms	103640 KB	Output is correct
54	Correct	200 ms	103780 KB	Output is correct
55	Correct	200 ms	103628 KB	Output is correct
56	Correct	29 ms	69652 KB	Output is correct
57	Correct	43 ms	73364 KB	Output is correct
58	Correct	112 ms	88848 KB	Output is correct
59	Correct	296 ms	106652 KB	Output is correct
60	Correct	134 ms	101436 KB	Output is correct
61	Correct	235 ms	100892 KB	Output is correct