Submission #203420

#	Time	Username	Problem	Language	Result	Execution time	Memory
203420		karma	Cat in a tree (BOI17_catinatree)	C++14	51 / 100	1082 ms	44348 KiB

catinatree

#include<bits/stdc++.h>
#define ll            long long
#define pb            emplace_back
#define fi            first
#define se            second
#define mp            make_pair
#define int           int64_t

using namespace std;

typedef pair<int, int> pii;
const int N = (int)2e5 + 10;

int dep[N], n, d, p[N], ans = 0;
int in[N], out[N], T, u, cur, par, rem;
vector<int> adj[N];
vector<pii> v;

struct TSegment {
    vector<int> l, h, st, lz;
    int n, inf;
    void init(int _n, int d) {
        n = ++_n; inf = 2 * d; st.resize(n << 2, inf);
        l.resize(n << 2), h.resize(n << 2), lz.resize(n << 2, inf);
        --n; build(1, 1, n);
    }
    void build(int x, int low, int high) {
        l[x] = low, h[x] = high;
        if(l[x] == h[x]) return;
        int mid = (l[x] + h[x]) >> 1;
        build(x << 1, low, mid);
        build(x << 1 | 1, mid + 1, high);
    }
    void change(int x, int val) {st[x] = min(st[x], val); lz[x] = min(lz[x], val);}
    void down(int x) {
        if(lz[x] == inf || l[x] == h[x]) return;
        change(x << 1, lz[x]), change(x << 1 | 1, lz[x]);
        lz[x] = inf;
    }
    void upd(int x, int low, int high, int val) {
        down(x);
        if(l[x] > high || h[x] < low) return;
        if(l[x] >= low && h[x] <= high) {
            st[x] = min(st[x], val);
            lz[x] = min(lz[x], val);
            return;
        }
        upd(x << 1, low, high, val); upd(x << 1 | 1, low, high, val);
        st[x] = min(st[x << 1], st[x << 1 | 1]);
    }
    int get(int x, int low, int high) {
        down(x);
        if(l[x] > high || h[x] < low) return inf;
        if(l[x] >= low && h[x] <= high) return st[x];
        return min(get(x << 1, low, high), get(x << 1 | 1, low, high));
    }
} it;

void DFS(int u) {
    in[u] = ++T;
    for(int v: adj[u]) DFS(v);
    out[u] = T;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define FileName      "test"
    if(fopen(FileName".inp", "r")) {
       freopen(FileName".inp", "r", stdin);
       freopen(FileName".out", "w", stdout);
    }
    cin >> n >> d; v.pb(0, 0);
    for(int i = 1; i < n; ++i) {
        cin >> p[i];
        adj[p[i]].pb(i);
        dep[i] = dep[p[i]] + 1;
        v.pb(dep[i], i);
    }
    sort(v.begin(), v.end(), greater<pii>());
    DFS(0); it.init(n, d);
    for(pii& node: v) {
        u = node.se; //cout << u << ' ' << it.get(1, in[u], in[u]) + dep[u] << '\n';
        if(it.get(1, in[u], in[u]) + dep[u] >= d) {
           ++ans; cur = u;
           while(1) {
              it.upd(1, in[cur], out[cur], dep[u] - 2 * dep[cur]);
              if(cur == 0) break;
              cur = p[cur];
           }
        }
    }
    cout << ans;
}

Compilation message (stderr)

catinatree.cpp: In function 'int32_t main()':
catinatree.cpp:70:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".inp", "r", stdin);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:71:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".out", "w", stdout);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 0 / 49