Submission #203426

#	Time	Username	Problem	Language	Result	Execution time	Memory
203426		karma	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	259 ms	20452 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 {
    int tree[N << 2], lim;
	void init() {
		memset(tree, 0x3f, sizeof(tree));
		for(lim = 1; lim <= n; lim <<= 1);
	}
	int get(int x){
		x += lim;
		int ret = 1e9;
		while(x){
			ret = min(ret, tree[x]);
			x >>= 1;
		}
		return ret;
	}
	void upd(int s, int e, int x){
		s += lim;
		e += lim;
		while(s < e){
			if(s%2 == 1) tree[s] = min(tree[s], x);
			if(e%2 == 0) tree[e] = min(tree[e], x);
			s = (s+1)/2;
			e = (e-1)/2;
		}
		if(s == e) tree[s] = min(tree[s], x);
	}
} 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);
//    }
    scanf("%d %d", &n, &d); v.pb(0, 0);
    for(int i = 1; i < n; ++i) {
        scanf("%d", &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();
    for(pii& node: v) {
        u = node.se;
        if(it.get(in[u]) + dep[u] >= d) {
           ++ans; cur = u;
           while(1) {
              it.upd(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:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &d); v.pb(0, 0);
     ~~~~~^~~~~~~~~~~~~~~~~
catinatree.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p[i]);
         ~~~~~^~~~~~~~~~~~~

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