제출 #1086551

#제출 시각아이디문제언어결과실행 시간메모리
1086551IBoryJobs (BOI24_jobs)C++17
14 / 100
2097 ms27520 KiB
#include <bits/stdc++.h> #define pii pair<ll, ll> typedef long long ll; using namespace std; const int MAX = 300003; vector<int> G[MAX]; ll S[MAX], P[MAX], V[MAX]; void PDFS(int cur) { vector<int> C; for (int next : G[cur]) { PDFS(next); if (S[next] >= 0) C.push_back(next); } for (int i = 1; i < C.size(); ++i) { if (G[C[0]].size() < G[C[i]].size()) { swap(S[C[0]], S[C[i]]); swap(G[C[0]], G[C[i]]); } S[C[0]] += S[C[i]]; S[C[i]] = 0; for (int next : G[C[i]]) { P[next] = S[C[0]]; G[C[0]].push_back(next); } G[C[i]].clear(); } } pii DFS(int cur, ll lim, ll down, ll up) { pii ret = {-1, cur}; if (!V[cur] && -down <= lim) ret = max(ret, pii{up, cur}); for (int next : G[cur]) { ret = max(ret, DFS(next, lim, min(down, up + S[next]), up + S[next])); } return ret; } int main() { ios::sync_with_stdio(0); cin.tie(0); ll N, init; cin >> N >> init; for (int i = 1; i <= N; ++i) { cin >> S[i] >> P[i]; G[P[i]].push_back(i); } PDFS(0); V[0] = 1; ll ans = init, cnt = 0; while (1) { auto [val, cur] = DFS(0, ans, 0, S[0]); if (val < 0) break; ans += val; while (cur && !V[cur]) { V[cur] = 1; S[cur] = 0; cur = P[cur]; } } cout << ans - init; return 0; }

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

Main.cpp: In function 'void PDFS(int)':
Main.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for (int i = 1; i < C.size(); ++i) {
      |                  ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:52:17: warning: unused variable 'cnt' [-Wunused-variable]
   52 |  ll ans = init, cnt = 0;
      |                 ^~~
#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...