oj.uz

Submission #717441

# Submission time Handle Problem Language Result Execution time Memory
717441 2023-04-01T23:15:46 Z vjudge1 Paths (RMI21_paths) C++17
36 / 100
 600 ms 26740 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;
const int off=(1<<20);
const int MOD = 1e9+7;
map<pair<int,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,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,v[i].S}]&&bl){
         bl=-1;
      }
      else val[hh].pb(v[i].F+mp[{x,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,r}]=v;
      mp[{r,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 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 10 ms 5300 KB Output is correct
4 Correct 9 ms 5332 KB Output is correct
5 Correct 10 ms 5332 KB Output is correct
6 Correct 9 ms 5204 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 10 ms 5300 KB Output is correct
4 Correct 9 ms 5332 KB Output is correct
5 Correct 10 ms 5332 KB Output is correct
6 Correct 9 ms 5204 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 276 ms 9328 KB Output is correct
9 Correct 280 ms 9456 KB Output is correct
10 Correct 239 ms 6276 KB Output is correct
11 Correct 247 ms 13352 KB Output is correct
12 Correct 250 ms 7448 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 10 ms 5300 KB Output is correct
4 Correct 9 ms 5332 KB Output is correct
5 Correct 10 ms 5332 KB Output is correct
6 Correct 9 ms 5204 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 276 ms 9328 KB Output is correct
9 Correct 280 ms 9456 KB Output is correct
10 Correct 239 ms 6276 KB Output is correct
11 Correct 247 ms 13352 KB Output is correct
12 Correct 250 ms 7448 KB Output is correct
13 Execution timed out 1080 ms 25732 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 26740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 10 ms 5300 KB Output is correct
4 Correct 9 ms 5332 KB Output is correct
5 Correct 10 ms 5332 KB Output is correct
6 Correct 9 ms 5204 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 276 ms 9328 KB Output is correct
9 Correct 280 ms 9456 KB Output is correct
10 Correct 239 ms 6276 KB Output is correct
11 Correct 247 ms 13352 KB Output is correct
12 Correct 250 ms 7448 KB Output is correct
13 Execution timed out 1080 ms 25732 KB Time limit exceeded
14 Halted 0 ms 0 KB -