이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
// }
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(n, d);
for(pii& node: v) {
u = node.se;
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;
}
컴파일 시 표준 에러 (stderr) 메시지
catinatree.cpp: In function 'int32_t main()':
catinatree.cpp:73: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:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p[i]);
~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |