oj.uz

Submission #717472

# Submission time Handle Problem Language Result Execution time Memory
717472 2023-04-02T00:50:47 Z MrM7md Paths (RMI21_paths) C++17
56 / 100
 370 ms 39408 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;
int mp[100000000];
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 1 ms 468 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 1 ms 468 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 3 ms 1480 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 3 ms 1492 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 1 ms 468 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 3 ms 1480 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 3 ms 1492 KB Output is correct
8 Correct 77 ms 10176 KB Output is correct
9 Correct 77 ms 10632 KB Output is correct
10 Correct 60 ms 7664 KB Output is correct
11 Correct 68 ms 13468 KB Output is correct
12 Correct 68 ms 8656 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 1 ms 468 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 3 ms 1480 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 3 ms 1492 KB Output is correct
8 Correct 77 ms 10176 KB Output is correct
9 Correct 77 ms 10632 KB Output is correct
10 Correct 60 ms 7664 KB Output is correct
11 Correct 68 ms 13468 KB Output is correct
12 Correct 68 ms 8656 KB Output is correct
13 Correct 360 ms 37876 KB Output is correct
14 Correct 370 ms 30328 KB Output is correct
15 Correct 266 ms 16704 KB Output is correct
16 Correct 292 ms 39408 KB Output is correct
17 Correct 307 ms 22464 KB Output is correct
18 Correct 202 ms 21924 KB Output is correct
19 Correct 368 ms 29776 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 468 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 1 ms 468 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 3 ms 1480 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 3 ms 1492 KB Output is correct
8 Correct 77 ms 10176 KB Output is correct
9 Correct 77 ms 10632 KB Output is correct
10 Correct 60 ms 7664 KB Output is correct
11 Correct 68 ms 13468 KB Output is correct
12 Correct 68 ms 8656 KB Output is correct
13 Correct 360 ms 37876 KB Output is correct
14 Correct 370 ms 30328 KB Output is correct
15 Correct 266 ms 16704 KB Output is correct
16 Correct 292 ms 39408 KB Output is correct
17 Correct 307 ms 22464 KB Output is correct
18 Correct 202 ms 21924 KB Output is correct
19 Correct 368 ms 29776 KB Output is correct
20 Runtime error 13 ms 468 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -