#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();
}
}
int profit=0;
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;
profit+=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 << profit;
}
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 |
166 ms |
225732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
211924 KB |
Output is correct |
2 |
Correct |
81 ms |
212052 KB |
Output is correct |
3 |
Correct |
88 ms |
212048 KB |
Output is correct |
4 |
Correct |
84 ms |
212020 KB |
Output is correct |
5 |
Correct |
97 ms |
212248 KB |
Output is correct |
6 |
Correct |
101 ms |
212052 KB |
Output is correct |
7 |
Correct |
98 ms |
212048 KB |
Output is correct |
8 |
Correct |
85 ms |
211996 KB |
Output is correct |
9 |
Correct |
86 ms |
212052 KB |
Output is correct |
10 |
Correct |
88 ms |
212048 KB |
Output is correct |
11 |
Correct |
100 ms |
212308 KB |
Output is correct |
12 |
Correct |
131 ms |
212048 KB |
Output is correct |
13 |
Correct |
88 ms |
212048 KB |
Output is correct |
14 |
Correct |
96 ms |
212048 KB |
Output is correct |
15 |
Correct |
87 ms |
212188 KB |
Output is correct |
16 |
Correct |
92 ms |
211932 KB |
Output is correct |
17 |
Correct |
102 ms |
212208 KB |
Output is correct |
18 |
Correct |
99 ms |
212052 KB |
Output is correct |
19 |
Correct |
87 ms |
212132 KB |
Output is correct |
20 |
Correct |
81 ms |
212048 KB |
Output is correct |
21 |
Correct |
90 ms |
212052 KB |
Output is correct |
22 |
Correct |
88 ms |
212048 KB |
Output is correct |
23 |
Correct |
100 ms |
212292 KB |
Output is correct |
24 |
Correct |
102 ms |
212052 KB |
Output is correct |
25 |
Correct |
90 ms |
212184 KB |
Output is correct |
26 |
Correct |
84 ms |
212084 KB |
Output is correct |
27 |
Correct |
87 ms |
212016 KB |
Output is correct |
28 |
Correct |
99 ms |
212052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
211924 KB |
Output is correct |
2 |
Correct |
81 ms |
212052 KB |
Output is correct |
3 |
Correct |
88 ms |
212048 KB |
Output is correct |
4 |
Correct |
84 ms |
212020 KB |
Output is correct |
5 |
Correct |
97 ms |
212248 KB |
Output is correct |
6 |
Correct |
101 ms |
212052 KB |
Output is correct |
7 |
Correct |
98 ms |
212048 KB |
Output is correct |
8 |
Correct |
85 ms |
211996 KB |
Output is correct |
9 |
Correct |
86 ms |
212052 KB |
Output is correct |
10 |
Correct |
88 ms |
212048 KB |
Output is correct |
11 |
Correct |
100 ms |
212308 KB |
Output is correct |
12 |
Correct |
131 ms |
212048 KB |
Output is correct |
13 |
Correct |
88 ms |
212048 KB |
Output is correct |
14 |
Correct |
96 ms |
212048 KB |
Output is correct |
15 |
Correct |
87 ms |
212188 KB |
Output is correct |
16 |
Correct |
92 ms |
211932 KB |
Output is correct |
17 |
Correct |
102 ms |
212208 KB |
Output is correct |
18 |
Correct |
99 ms |
212052 KB |
Output is correct |
19 |
Correct |
87 ms |
212132 KB |
Output is correct |
20 |
Correct |
81 ms |
212048 KB |
Output is correct |
21 |
Correct |
90 ms |
212052 KB |
Output is correct |
22 |
Correct |
88 ms |
212048 KB |
Output is correct |
23 |
Correct |
100 ms |
212292 KB |
Output is correct |
24 |
Correct |
102 ms |
212052 KB |
Output is correct |
25 |
Correct |
90 ms |
212184 KB |
Output is correct |
26 |
Correct |
84 ms |
212084 KB |
Output is correct |
27 |
Correct |
87 ms |
212016 KB |
Output is correct |
28 |
Correct |
99 ms |
212052 KB |
Output is correct |
29 |
Correct |
162 ms |
225360 KB |
Output is correct |
30 |
Correct |
173 ms |
223692 KB |
Output is correct |
31 |
Correct |
154 ms |
226580 KB |
Output is correct |
32 |
Correct |
158 ms |
243400 KB |
Output is correct |
33 |
Correct |
147 ms |
234400 KB |
Output is correct |
34 |
Correct |
138 ms |
229324 KB |
Output is correct |
35 |
Correct |
120 ms |
218728 KB |
Output is correct |
36 |
Correct |
160 ms |
224472 KB |
Output is correct |
37 |
Correct |
159 ms |
224848 KB |
Output is correct |
38 |
Correct |
159 ms |
244164 KB |
Output is correct |
39 |
Correct |
147 ms |
235464 KB |
Output is correct |
40 |
Correct |
147 ms |
227272 KB |
Output is correct |
41 |
Correct |
144 ms |
225732 KB |
Output is correct |
42 |
Correct |
117 ms |
219732 KB |
Output is correct |
43 |
Correct |
154 ms |
227668 KB |
Output is correct |
44 |
Correct |
154 ms |
244428 KB |
Output is correct |
45 |
Correct |
156 ms |
235204 KB |
Output is correct |
46 |
Correct |
159 ms |
229584 KB |
Output is correct |
47 |
Correct |
153 ms |
225696 KB |
Output is correct |
48 |
Correct |
201 ms |
224864 KB |
Output is correct |
49 |
Correct |
171 ms |
224608 KB |
Output is correct |
50 |
Correct |
171 ms |
244928 KB |
Output is correct |
51 |
Correct |
139 ms |
228136 KB |
Output is correct |
52 |
Correct |
142 ms |
227488 KB |
Output is correct |
53 |
Correct |
139 ms |
224080 KB |
Output is correct |
54 |
Correct |
190 ms |
225304 KB |
Output is correct |
55 |
Correct |
184 ms |
224592 KB |
Output is correct |
56 |
Correct |
161 ms |
245180 KB |
Output is correct |
57 |
Correct |
158 ms |
234436 KB |
Output is correct |
58 |
Correct |
145 ms |
227284 KB |
Output is correct |
59 |
Correct |
146 ms |
226900 KB |
Output is correct |
60 |
Correct |
152 ms |
224856 KB |
Output is correct |
61 |
Correct |
158 ms |
227576 KB |
Output is correct |
62 |
Correct |
155 ms |
228044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
211924 KB |
Output is correct |
2 |
Correct |
81 ms |
212052 KB |
Output is correct |
3 |
Correct |
88 ms |
212048 KB |
Output is correct |
4 |
Correct |
84 ms |
212020 KB |
Output is correct |
5 |
Correct |
97 ms |
212248 KB |
Output is correct |
6 |
Correct |
101 ms |
212052 KB |
Output is correct |
7 |
Correct |
98 ms |
212048 KB |
Output is correct |
8 |
Correct |
85 ms |
211996 KB |
Output is correct |
9 |
Correct |
86 ms |
212052 KB |
Output is correct |
10 |
Correct |
88 ms |
212048 KB |
Output is correct |
11 |
Correct |
100 ms |
212308 KB |
Output is correct |
12 |
Correct |
131 ms |
212048 KB |
Output is correct |
13 |
Correct |
88 ms |
212048 KB |
Output is correct |
14 |
Correct |
96 ms |
212048 KB |
Output is correct |
15 |
Correct |
87 ms |
212188 KB |
Output is correct |
16 |
Correct |
92 ms |
211932 KB |
Output is correct |
17 |
Correct |
102 ms |
212208 KB |
Output is correct |
18 |
Correct |
99 ms |
212052 KB |
Output is correct |
19 |
Correct |
87 ms |
212132 KB |
Output is correct |
20 |
Correct |
81 ms |
212048 KB |
Output is correct |
21 |
Correct |
90 ms |
212052 KB |
Output is correct |
22 |
Correct |
88 ms |
212048 KB |
Output is correct |
23 |
Correct |
100 ms |
212292 KB |
Output is correct |
24 |
Correct |
102 ms |
212052 KB |
Output is correct |
25 |
Correct |
90 ms |
212184 KB |
Output is correct |
26 |
Correct |
84 ms |
212084 KB |
Output is correct |
27 |
Correct |
87 ms |
212016 KB |
Output is correct |
28 |
Correct |
99 ms |
212052 KB |
Output is correct |
29 |
Incorrect |
90 ms |
212052 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
166 ms |
225732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |