#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];
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});
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;
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});
}
}
while(!pq.empty()){
//if can absorb then absorb
pair<pii,int>cur=pq.top();
pq.pop();
if(m>=cur.first.first){
m+=cur.first.second;
}
ptr[cur.second]++;
if(ptr[cur.second]<(int)storage[cur.second].size()){
pq.push({storage[cur.second][ptr[cur.second]],cur.second});
}
}
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();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
68 ms |
30756 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
16984 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
16984 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
16984 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
68 ms |
30756 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |