oj.uz

Submission #718305

# Submission time Handle Problem Language Result Execution time Memory
718305 2023-04-03T20:10:02 Z MrM7md Paths (RMI21_paths) C++17
19 / 100
 22 ms 14548 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=1e5+20;
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 3 ms 5216 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5216 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 7 ms 6544 KB Output is correct
4 Correct 7 ms 6400 KB Output is correct
5 Correct 7 ms 6528 KB Output is correct
6 Correct 6 ms 6356 KB Output is correct
7 Correct 6 ms 6484 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5216 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 7 ms 6544 KB Output is correct
4 Correct 7 ms 6400 KB Output is correct
5 Correct 7 ms 6528 KB Output is correct
6 Correct 6 ms 6356 KB Output is correct
7 Correct 6 ms 6484 KB Output is correct
8 Runtime error 22 ms 14548 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5216 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 7 ms 6544 KB Output is correct
4 Correct 7 ms 6400 KB Output is correct
5 Correct 7 ms 6528 KB Output is correct
6 Correct 6 ms 6356 KB Output is correct
7 Correct 6 ms 6484 KB Output is correct
8 Runtime error 22 ms 14548 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 5076 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 3 ms 5216 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 7 ms 6544 KB Output is correct
4 Correct 7 ms 6400 KB Output is correct
5 Correct 7 ms 6528 KB Output is correct
6 Correct 6 ms 6356 KB Output is correct
7 Correct 6 ms 6484 KB Output is correct
8 Runtime error 22 ms 14548 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -