oj.uz

Submission #718303

# Submission time Handle Problem Language Result Execution time Memory
718303 2023-04-03T20:07:17 Z MrM7md Paths (RMI21_paths) C++17
56 / 100
 383 ms 41552 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=3e4;
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 1768 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1768 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 5 ms 2900 KB Output is correct
4 Correct 5 ms 2900 KB Output is correct
5 Correct 6 ms 2912 KB Output is correct
6 Correct 5 ms 2772 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1768 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 5 ms 2900 KB Output is correct
4 Correct 5 ms 2900 KB Output is correct
5 Correct 6 ms 2912 KB Output is correct
6 Correct 5 ms 2772 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 84 ms 11820 KB Output is correct
9 Correct 89 ms 12292 KB Output is correct
10 Correct 85 ms 9372 KB Output is correct
11 Correct 73 ms 15172 KB Output is correct
12 Correct 69 ms 10340 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1768 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 5 ms 2900 KB Output is correct
4 Correct 5 ms 2900 KB Output is correct
5 Correct 6 ms 2912 KB Output is correct
6 Correct 5 ms 2772 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 84 ms 11820 KB Output is correct
9 Correct 89 ms 12292 KB Output is correct
10 Correct 85 ms 9372 KB Output is correct
11 Correct 73 ms 15172 KB Output is correct
12 Correct 69 ms 10340 KB Output is correct
13 Correct 362 ms 40048 KB Output is correct
14 Correct 383 ms 32420 KB Output is correct
15 Correct 309 ms 18696 KB Output is correct
16 Correct 310 ms 41552 KB Output is correct
17 Correct 314 ms 24524 KB Output is correct
18 Correct 210 ms 23904 KB Output is correct
19 Correct 376 ms 31732 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 1876 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 1768 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 5 ms 2900 KB Output is correct
4 Correct 5 ms 2900 KB Output is correct
5 Correct 6 ms 2912 KB Output is correct
6 Correct 5 ms 2772 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 84 ms 11820 KB Output is correct
9 Correct 89 ms 12292 KB Output is correct
10 Correct 85 ms 9372 KB Output is correct
11 Correct 73 ms 15172 KB Output is correct
12 Correct 69 ms 10340 KB Output is correct
13 Correct 362 ms 40048 KB Output is correct
14 Correct 383 ms 32420 KB Output is correct
15 Correct 309 ms 18696 KB Output is correct
16 Correct 310 ms 41552 KB Output is correct
17 Correct 314 ms 24524 KB Output is correct
18 Correct 210 ms 23904 KB Output is correct
19 Correct 376 ms 31732 KB Output is correct
20 Runtime error 11 ms 1876 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -