oj.uz

Submission #717473

# Submission time Handle Problem Language Result Execution time Memory
717473 2023-04-02T00:51:04 Z vjudge1 Paths (RMI21_paths) C++17
56 / 100
 403 ms 39344 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 4 ms 1492 KB Output is correct
6 Correct 4 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 4 ms 1492 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 3 ms 1492 KB Output is correct
8 Correct 82 ms 10156 KB Output is correct
9 Correct 83 ms 10580 KB Output is correct
10 Correct 63 ms 7708 KB Output is correct
11 Correct 69 ms 13492 KB Output is correct
12 Correct 64 ms 8592 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 4 ms 1492 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 3 ms 1492 KB Output is correct
8 Correct 82 ms 10156 KB Output is correct
9 Correct 83 ms 10580 KB Output is correct
10 Correct 63 ms 7708 KB Output is correct
11 Correct 69 ms 13492 KB Output is correct
12 Correct 64 ms 8592 KB Output is correct
13 Correct 352 ms 37988 KB Output is correct
14 Correct 403 ms 30288 KB Output is correct
15 Correct 305 ms 16644 KB Output is correct
16 Correct 284 ms 39344 KB Output is correct
17 Correct 313 ms 22344 KB Output is correct
18 Correct 198 ms 21964 KB Output is correct
19 Correct 335 ms 29732 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 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 4 ms 1492 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 3 ms 1492 KB Output is correct
8 Correct 82 ms 10156 KB Output is correct
9 Correct 83 ms 10580 KB Output is correct
10 Correct 63 ms 7708 KB Output is correct
11 Correct 69 ms 13492 KB Output is correct
12 Correct 64 ms 8592 KB Output is correct
13 Correct 352 ms 37988 KB Output is correct
14 Correct 403 ms 30288 KB Output is correct
15 Correct 305 ms 16644 KB Output is correct
16 Correct 284 ms 39344 KB Output is correct
17 Correct 313 ms 22344 KB Output is correct
18 Correct 198 ms 21964 KB Output is correct
19 Correct 335 ms 29732 KB Output is correct
20 Runtime error 12 ms 468 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -