제출 #796492

#제출 시각아이디문제언어결과실행 시간메모리
796492MadokaMagicaFanCat in a tree (BOI17_catinatree)C++14
0 / 100
3 ms4948 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; 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); 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)); } } 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); 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;; }

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

catinatree.cpp: In function 'int32_t main(int32_t, char**)':
catinatree.cpp:80:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  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...