# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
871027 |
2023-11-09T17:54:38 Z |
Ahmed57 |
Paths (RMI21_paths) |
C++17 |
|
435 ms |
700 KB |
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,long long>> adj[2001];
int in[2001],outt[2001];
pair<long long,long long>P[2001];int decode[2001];int timer = 0;
pair<long long,long long> seg[8001];long long lazy[8001];
void build(int p,int l,int r){
lazy[p] = 0;
if(l==r){
seg[p].second = decode[l];
seg[p].first = 0;
return;
}
int md = (l+r)/2;
build(p*2,l,md);
build(p*2+1,md+1,r);
seg[p] = max(seg[p*2],seg[p*2+1]);
}
void prop(int p,int l,int r){
seg[p].first+=lazy[p];
if(l!=r){
lazy[p*2]+=lazy[p];
lazy[p*2+1]+=lazy[p];
}
lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,long long val){
prop(p,l,r);
if(l>=lq&&r<=rq){
lazy[p]+=val;
prop(p,l,r);
return ;
}
if(r<lq||l>rq)return ;
int md = (l+r)/2;
update(p*2,l,md,lq,rq,val);
update(p*2+1,md+1,r,lq,rq,val);
seg[p] = max(seg[p*2],seg[p*2+1]);
}
void dfs(int i,int pr){
in[i] = ++timer;
decode[timer] = i;
for(auto j:adj[i]){
if(j.first==pr)continue;
dfs(j.first,i);
}
outt[i] = timer;
}
int n;
void go(int i,int pr,long long la){
P[i] = {pr,la};
for(auto j:adj[i]){
if(j.first==pr)continue;
update(1,1,n,in[j.first],outt[j.first],j.second);
go(j.first,i,j.second);
}
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int k;
cin>>n>>k;
for(int i = 0;i<n-1;i++){
int a,b,c;cin>>a>>b>>c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
for(int r = 1;r<=n;r++){
timer = 0;
dfs(r,0);
build(1,1,n);
go(r,0,0);
int e = k;
long long all = 0;
while(e--){
int no = seg[1].second;
while(no!=r){
if(P[no].second==0){
break;
}
update(1,1,n,in[no],outt[no],-P[no].second);
all+=P[no].second;
P[no].second = 0;
no = P[no].first;
}
}
cout<<all<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
10 ms |
348 KB |
Output is correct |
4 |
Correct |
14 ms |
348 KB |
Output is correct |
5 |
Correct |
9 ms |
348 KB |
Output is correct |
6 |
Correct |
15 ms |
348 KB |
Output is correct |
7 |
Correct |
12 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
10 ms |
348 KB |
Output is correct |
4 |
Correct |
14 ms |
348 KB |
Output is correct |
5 |
Correct |
9 ms |
348 KB |
Output is correct |
6 |
Correct |
15 ms |
348 KB |
Output is correct |
7 |
Correct |
12 ms |
348 KB |
Output is correct |
8 |
Correct |
296 ms |
664 KB |
Output is correct |
9 |
Correct |
435 ms |
700 KB |
Output is correct |
10 |
Incorrect |
319 ms |
600 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
10 ms |
348 KB |
Output is correct |
4 |
Correct |
14 ms |
348 KB |
Output is correct |
5 |
Correct |
9 ms |
348 KB |
Output is correct |
6 |
Correct |
15 ms |
348 KB |
Output is correct |
7 |
Correct |
12 ms |
348 KB |
Output is correct |
8 |
Correct |
296 ms |
664 KB |
Output is correct |
9 |
Correct |
435 ms |
700 KB |
Output is correct |
10 |
Incorrect |
319 ms |
600 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
10 ms |
348 KB |
Output is correct |
4 |
Correct |
14 ms |
348 KB |
Output is correct |
5 |
Correct |
9 ms |
348 KB |
Output is correct |
6 |
Correct |
15 ms |
348 KB |
Output is correct |
7 |
Correct |
12 ms |
348 KB |
Output is correct |
8 |
Correct |
296 ms |
664 KB |
Output is correct |
9 |
Correct |
435 ms |
700 KB |
Output is correct |
10 |
Incorrect |
319 ms |
600 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |