oj.uz

Submission #717471

# Submission time Handle Problem Language Result Execution time Memory
717471 2023-04-02T00:48:46 Z MrM7md Paths (RMI21_paths) C++17
36 / 100
 600 ms 22204 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;
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 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 8 ms 620 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 6 ms 596 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 8 ms 620 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 267 ms 4588 KB Output is correct
9 Correct 248 ms 4724 KB Output is correct
10 Correct 208 ms 1752 KB Output is correct
11 Correct 246 ms 8676 KB Output is correct
12 Correct 222 ms 2660 KB Output is correct

Subtask #4
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 8 ms 620 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 267 ms 4588 KB Output is correct
9 Correct 248 ms 4724 KB Output is correct
10 Correct 208 ms 1752 KB Output is correct
11 Correct 246 ms 8676 KB Output is correct
12 Correct 222 ms 2660 KB Output is correct
13 Execution timed out 1077 ms 22204 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 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 8 ms 620 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 267 ms 4588 KB Output is correct
9 Correct 248 ms 4724 KB Output is correct
10 Correct 208 ms 1752 KB Output is correct
11 Correct 246 ms 8676 KB Output is correct
12 Correct 222 ms 2660 KB Output is correct
13 Execution timed out 1077 ms 22204 KB Time limit exceeded
14 Halted 0 ms 0 KB -