oj.uz

Submission #717474

# Submission time Handle Problem Language Result Execution time Memory
717474 2023-04-02T00:51:58 Z MrM7md Paths (RMI21_paths) C++17
56 / 100
 486 ms 28212 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
const int N=3e3;
const int off=(1<<20);
const int MOD = 1e9+7;
unordered_map<int,int>mp;
vector<vector<int>>gr(N),val(N);
bool vis[N];
int ahhhh[N];

int dfs(int x,int hh){
   vis[x]=1;
   int mx=0;
   vector<pair<int,int>>v;
   if(gr[x].size()==1){
      ahhhh[hh]++;
   }
   for(auto it:gr[x]){
      if(!vis[it]){
         int ahh=dfs(it,hh);
         mx=max(mx,ahh+mp[x*N+it]);
         v.pb({ahh,it});
         // cout<<ahh<<' ';
      }
   }
   bool bl=1;
   for(int i=0;i<v.size();i++){
      if(mx==v[i].F+mp[x*N+v[i].S]&&bl){
         bl=-1;
      }
      else val[hh].pb(v[i].F+mp[x*N+v[i].S]);
   }
   return mx;
}

signed main(){
   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   int n,k;
   cin >> n>>k;
   for(int i=1;i<n;i++){
      int l,r,v;
      cin >> l >> r >> v;
      gr[l].pb(r);
      gr[r].pb(l);
      mp[l*N+r]=v;
      mp[r*N+l]=v;
   }
   for(int i=1;i<=n;i++){
      memset(vis,0,sizeof(vis));
      int r=dfs(i,i);
      val[i].pb(r);
      sort(all(val[i]));
      int cnt=0;
      for(int w=val[i].size()-1;w>=val[i].size()-min(ahhhh[i],k);w--){
         cnt+=val[i][w];
      }
      cout<<cnt<<endl;
   }

}
/*

*/

Compilation message

Main.cpp: In function 'long long int dfs(long long int, long long int)':
Main.cpp:33:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for(int i=0;i<v.size();i++){
      |                ~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:60:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   60 |       for(int w=val[i].size()-1;w>=val[i].size()-min(ahhhh[i],k);w--){
      |                                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 4 ms 664 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 596 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 4 ms 664 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 105 ms 4692 KB Output is correct
9 Correct 101 ms 4664 KB Output is correct
10 Correct 79 ms 1600 KB Output is correct
11 Correct 95 ms 8628 KB Output is correct
12 Correct 85 ms 2528 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 4 ms 664 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 105 ms 4692 KB Output is correct
9 Correct 101 ms 4664 KB Output is correct
10 Correct 79 ms 1600 KB Output is correct
11 Correct 95 ms 8628 KB Output is correct
12 Correct 85 ms 2528 KB Output is correct
13 Correct 445 ms 25028 KB Output is correct
14 Correct 486 ms 16984 KB Output is correct
15 Correct 317 ms 2960 KB Output is correct
16 Correct 404 ms 28212 KB Output is correct
17 Correct 382 ms 8772 KB Output is correct
18 Correct 242 ms 12740 KB Output is correct
19 Correct 445 ms 16716 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 4 ms 664 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 105 ms 4692 KB Output is correct
9 Correct 101 ms 4664 KB Output is correct
10 Correct 79 ms 1600 KB Output is correct
11 Correct 95 ms 8628 KB Output is correct
12 Correct 85 ms 2528 KB Output is correct
13 Correct 445 ms 25028 KB Output is correct
14 Correct 486 ms 16984 KB Output is correct
15 Correct 317 ms 2960 KB Output is correct
16 Correct 404 ms 28212 KB Output is correct
17 Correct 382 ms 8772 KB Output is correct
18 Correct 242 ms 12740 KB Output is correct
19 Correct 445 ms 16716 KB Output is correct
20 Runtime error 1 ms 724 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -