# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
994583 |
2024-06-08T01:57:23 Z |
LCJLY |
Jobs (BOI24_jobs) |
C++14 |
|
175 ms |
225732 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
vector<int>adj[300005];
int arr[300005];
bool visited[300005];
//vector<pii>storage[300005];
queue<pii>que[300005];
vector<pii>component;
int mini=0;
int counter=0;
void dfs(int index){
counter+=arr[index];
mini=min(mini,counter);
visited[index]=true;
if(counter>0){
component.push_back({mini,counter});
//show2(mini,mini,counter,counter);
counter=0;
mini=0;
}
for(auto it:adj[index]){
if(visited[it]) continue;
dfs(it);
}
}
void solve(){
int n,m;
cin >> n >> m;
//show2(n,n,m,m);
int temp,temp2;
for(int x=1;x<=n;x++){
cin >> temp >> temp2;
swap(temp,temp2);
if(temp!=0){
adj[temp].push_back(x);
}
arr[x]=temp2;
}
for(int x=1;x<=n;x++){
if(visited[x]) continue;
mini=0;
counter=0;
dfs(x);
//storage[x]=component;
for(auto it:component) que[x].push(it);
component.clear();
}
int ptr[n+5];
memset(ptr,0,sizeof(ptr));
//show(done,2);
priority_queue<pair<pii,int>>pq;
for(int x=1;x<=n;x++){
//if(!storage[x].empty()){
//pq.push({storage[x][0],x});
//}
if(!que[x].empty()){
pq.push({que[x].front(),x});
que[x].pop();
}
}
while(!pq.empty()){
//if can absorb then absorb
pair<pii,int>cur=pq.top();
pq.pop();
//show2(m,m,cur.first.first,cur.first.first);
if(m+cur.first.first>=0){
m+=cur.first.second;
}
else break;
//ptr[cur.second]++;
//if(ptr[cur.second]<(int)storage[cur.second].size()){
//pq.push({storage[cur.second][ptr[cur.second]],cur.second});
//}
if(!que[cur.second].empty()){
pq.push({que[cur.second].front(),cur.second});
que[cur.second].pop();
}
}
cout << m;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
//freopen("in.txt","r",stdin);
while(t--){
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
175 ms |
225732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
85 ms |
212048 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
85 ms |
212048 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
85 ms |
212048 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
175 ms |
225732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |