제출 #1001153

#제출 시각아이디문제언어결과실행 시간메모리
1001153LOLOLOJobs (BOI24_jobs)C++17
0 / 100
293 ms104712 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (ll)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 3e5 + 10; vector <int> ed[N], ed2[N]; int p[N][20], in[N], ou[N], timer = 1; ll mi[N][20], dep[N]; void dfs(int u, ll mx, int cur) { if (dep[u] > mx) { ed2[cur].pb(u); mx = dep[u]; cur = u; } mi[u][0] = dep[u]; for (int j = 1; j < 20; j++) { mi[u][j] = min(mi[u][j - 1], mi[p[u][j - 1]][j - 1]); } in[u] = ++timer; for (auto x : ed[u]) { dep[x] = dep[u] + dep[x]; dfs(x, mx, cur); } ou[u] = timer; } bool is(int a, int b) { return in[a] <= in[b] && ou[a] >= in[b]; } ll path(int a, int b) { ll pr = 1e18; for (int j = 19; j >= 0; j--) { if (is(a, p[b][j]) == 0) { pr = min(pr, mi[b][j]); b = p[b][j]; } } return pr; } ll solve() { int n; ll s; cin >> n >> s; for (int i = 1; i <= n; i++) { cin >> dep[i] >> p[i][0]; ed[p[i][0]].pb(i); } for (int j = 1; j < 20; j++) for (int i = 1; i <= n; i++) p[i][j] = p[p[i][j - 1]][j - 1]; dfs(0, 0, 0); priority_queue <vector <ll>> pq; for (auto x : ed2[0]) { pq.push({path(0, x) - dep[x], dep[x] - dep[0], x}); } ll st = s; while (sz(pq)) { auto t = pq.top(); pq.pop(); if (s + t[0] >= 0) { s += t[1]; } else { break; } for (auto x : ed2[t[2]]) { pq.push({path(t[2], x) - dep[t[2]], dep[x] - dep[t[2]], x}); } } return s - st; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { cout << solve() << '\n'; } return 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...