제출 #796502

#제출 시각아이디문제언어결과실행 시간메모리
796502MadokaMagicaFanCat in a tree (BOI17_catinatree)C++14
0 / 100
5 ms9684 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const int N = 2e5; int p[N]; int h[N]; int __n, d, inf; vector<int> adj[N]; struct aint { int n; vector<int> f; aint(int _n) { n = _n; f.assign(n<<1, 0); } int query(int l, int r) { l += n; r += n+1; if (l >= 2*n-1) return 0; r = min(r, 2*n); int ans = 0; for (; l < r; l >>= 1, r >>= 1) { if (l&1) ans = max(ans, f[l++]); if (r&1) ans = max(ans, f[--r]); } return ans; } int getv(int x) { return f[x+n]; } void upd(int x, int v) { x += n; for (f[x] = max(v, f[x]); x > 1; x>>=1) { f[x>>1] = max(f[x], f[x^1]); } } }; vector<aint> t; vector<int> lp[N]; int tp[N]; int mx1[N]; int mx2[N]; void dfs(int x) { if (x) h[x] = h[p[x]] + 1; int _h, v, j; for (auto u : adj[x]) dfs(u); // v = 1 + t[x].query(h[x]+d, inf); // t[x].upd(h[x], v); v = 0; for (int i = h[x] + d; i < __n; ++i) v = max(v, lp[x][i]); ++v; lp[x][h[x]] = v; if (!x) return; j = p[x]; /* for (int z = __n-1; z >= h[x]; --z) { _h = max(2*h[j] + d - z, h[j]); t[j].upd(min(_h, z), t[j].query(_h, inf) + t[x].query(z, inf)); } for (int z = h[x]; z < __n; ++z) { if (2*(z - h[j]) >= d) t[j].upd(z, t[x].query(z, inf) + t[j].query(z,inf)); } for (int z = __n-1; z >= h[x]; --z) { t[j].upd(z, t[x].getv(z)); } */ for (int i = 0; i < __n; ++i) tp[i] = 0; mx1[__n-1] = lp[x][__n-1]; mx2[__n-1] = lp[j][__n-1]; for (int i = __n-2; i >= h[j]; --i) { mx1[i] = max(mx1[i-1], lp[x][i]); mx2[i] = max(mx2[i-1], lp[j][i]); } for (int u = h[x]; u < __n; ++u) { tp[u] = max(mx1[u], mx2[u]); for (int z = u; z < __n; ++z) { _h = max(2*h[j] + d - z, h[j]); _h = max(u, _h); tp[u] = max(tp[u], mx1[z] + mx2[_h]); } } for (int i = h[j]; i < __n; ++i) lp[j][i] = tp[i]; } int32_t main(int32_t argc, char *argv[]) { if (argc > 1) freopen(argv[1], "r", stdin); int n; cin >> n >> d; __n = n; inf = 2*n + 5; p[0] = 0; for (int i = 1; i < n; ++i) { cin >> p[i]; adj[p[i]].push_back(i); } for (int i = 0; i <n; ++i) t.emplace(t.end() ,n); for (int i = 0; i <n; ++i) lp[i].assign(n, 0); h[0] = 0; dfs(0); /* for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) cout << t[i].getv(j); cout<< endl; } cout << t[0].query(0, inf) << endl;; */ int ans = 0; for (int i = 0; i < n; ++i) ans = max(ans, lp[0][i]); cout << ans << endl; }

컴파일 시 표준 에러 (stderr) 메시지

catinatree.cpp: In function 'int32_t main(int32_t, char**)':
catinatree.cpp:117:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  if (argc > 1) freopen(argv[1], "r", stdin);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...