제출 #313819

#제출 시각아이디문제언어결과실행 시간메모리
313819BeanZ무제 (POI11_dyn)C++14
100 / 100
1997 ms36984 KiB
// I_Love_LPL #include <bits/stdc++.h> using namespace std; #define ll int #define endl '\n' const int N = 3e5 + 5; ll cnt = 0, mid; ll dp[N], hp[N], a[N], farcry[N]; vector<ll> node[N]; void dfs(ll u, ll p){ hp[u] = 0; for (auto j : node[u]){ if (j == p) continue; dfs(j, u); farcry[u] = min(farcry[u], farcry[j] + 1); } if (a[u] == 1 && farcry[u] > mid) hp[u] = 1, dp[u] = 0; for (auto j : node[u]){ if (j == p) continue; if (hp[j]){ if ((farcry[u] + dp[j] + 1) <= mid) continue; else dp[u] = max(dp[u], dp[j] + 1), hp[u] = 1; } } if (dp[u] == mid){ cnt++; dp[u] = -1e9; farcry[u] = 0; hp[u] = 0; } if (u == 1){ if (dp[u] == 0 && a[u] && farcry[u] > mid) cnt++; else if (dp[u] >= 1) cnt++; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("A.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n, m; cin >> n >> m; ll res = 0; for (int i = 1; i <= n; i++){ cin >> a[i]; if (a[i] == 1) res++; } for (int i = 1; i < n; i++){ ll u, v; cin >> u >> v; node[u].push_back(v); node[v].push_back(u); } if (res <= m) return cout << 0, 0; ll l = 1, h = n; while (l <= h){ mid = (l + h) >> 1; cnt = 0; memset(hp, 0, sizeof(hp)); for (int i = 1; i <= n; i++) farcry[i] = 1e9, dp[i] = -1e9; dfs(1, 1); if (cnt > m) l = mid + 1; else h = mid - 1; } cout << l; } /* */

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

dyn.cpp: In function 'int main()':
dyn.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dyn.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...