Submission #514685

#	Time	Username	Problem	Language	Result	Execution time	Memory
514685		kshitij_sodani	Paths (RMI21_paths)	C++14	56 / 100	1089 ms	10024 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,k;
vector<pair<llo,llo>> adj[100001];
llo ans[100001];
pair<llo,llo> val[100001];

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define ord tree<pair<llo,llo>,null_type,greater<pair<llo,llo>>,rb_tree_tag,tree_order_statistics_node_update>
ord cur;
vector<llo> cur2;
void dfs(llo no,llo par=-1){
	vector<pair<llo,llo>> ss;
	for(auto j:adj[no]){
		if(j.a!=par){
			
			dfs(j.a,no);
			ss.pb({val[j.a].a+j.b,val[j.a].b});
		}
	}
	if(ss.size()==0){
		val[no]={0,no};
		return;
	}
	sort(ss.begin(),ss.end());
	for(llo j=0;j<ss.size();j++){
		if(j+1==ss.size()){
			val[no]=ss[j];
		}
		else{
			cur2.pb(ss[j].a);
			//cur.insert(ss[j]);
		}
	}
}
llo su=0;
void dfs2(llo no,llo par=-1){
	ans[no]=su;
	for(auto j:adj[no]){
		if(j.a!=par){
			int x=cur.order_of_key({val[j.a].a+j.b,val[j.a].b});
			llo su2=su;
			
			cur.erase({val[j.a].a+j.b,val[j.a].b});
			if(x<k){
				su-=(val[j.a].a+j.b);
				if(cur.size()>=k){
					su+=(*cur.find_by_order(k-1)).a;
				}
			}
			if(cur.order_of_key({val[j.a].a,val[j.a].b})<k){
				if(cur.size()>=k){
					su-=(*cur.find_by_order(k-1)).a;
				}
				su+=val[j.a].a;
			}
			cur.insert({val[j.a].a,val[j.a].b});
			dfs2(j.a,no);
			su=su2;

		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	llo ma=0;
	for(llo i=0;i<n-1;i++){
		llo aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		ma=cc;
		adj[aa].pb({bb,cc});
		adj[bb].pb({aa,cc});
	}
	
	if(n==1){
		cout<<0<<endl;
		return 0;
	}
	if(n==2){
		cout<<ma<<endl;
		cout<<ma<<endl;
		return 0;
	}
	for(int i=0;i<n;i++){
		cur2.clear();
		dfs(i);
		llo ans2=0;
		//cur.insert(val[i]);
		cur2.pb(val[i].a);
		sort(cur2.begin(),cur2.end());
		reverse(cur2.begin(),cur2.end());
		for(llo j=0;j<k;j++){
			if(j>=cur2.size()){
				continue;
			}
			ans2+=cur2[j];
		}
		cout<<ans2<<endl;
	}
/*	llo ind=0;
	for(llo i=0;i<n;i++){
		if(adj[i].size()>1){
			ind=i;
		}
	}
	dfs(ind);
	k=min(k,(llo)(cur.size()));
	
	cur.insert(val[ind]);
	for(llo j=0;j<k;j++){
		su+=(*cur.find_by_order(j)).a;
	}
	for(auto j:cur){
		cout<<j.a<<":"<<j.b<<endl;
	}
	cout<<ind<<":"<<su<<endl;
	dfs2(ind);
	for(int i=0;i<n;i++){
		cout<<ans[i]<<endl;
	}
*/


 
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(llo, llo)':
Main.cpp:35:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(llo j=0;j<ss.size();j++){
      |              ~^~~~~~~~~~
Main.cpp:36:9: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   if(j+1==ss.size()){
      |      ~~~^~~~~~~~~~~
Main.cpp: In function 'void dfs2(llo, llo)':
Main.cpp:56:18: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'llo' {aka 'long long int'} [-Wsign-compare]
   56 |     if(cur.size()>=k){
      |        ~~~~~~~~~~^~~
Main.cpp:60:48: warning: comparison of integer expressions of different signedness: '__gnu_pbds::tree_order_statistics_node_update<__gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<long long int, long long int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<long long int, long long int>, long unsigned int, std::allocator<char> >*, std::pair<long long int, long long int>, std::pair<long long int, long long int>*, const std::pair<long long int, long long int>*, std::pair<long long int, long long int>&, const std::pair<long long int, long long int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<long long int, long long int>, long unsigned int, std::allocator<char> >*, std::pair<long long int, long long int>, std::pair<long long int, long long int>*, const std::pair<long long int, long long int>*, std::pair<long long int, long long int>&, const std::pair<long long int, long long int>&, true, std::allocator<char> >, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<long long int, long long int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<long long int, long long int>, long unsigned int, std::allocator<char> >*, std::pair<long long int, long long int>, std::pair<long long int, long long int>*, const std::pair<long long int, long long int>*, std::pair<long long int, long long int>&, const std::pair<long long int, long long int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<long long int, long long int>, long unsigned int, std::allocator<char> >*, std::pair<long long int, long long int>, std::pair<long long int, long long int>*, const std::pair<long long int, long long int>*, std::pair<long long int, long long int>&, const std::pair<long long int, long long int>&, true, std::allocator<char> >, std::allocator<char> >, std::greater<std::pair<long long int, long long int> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'llo' {aka 'long long int'} [-Wsign-compare]
   60 |    if(cur.order_of_key({val[j.a].a,val[j.a].b})<k){
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
Main.cpp:61:18: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'llo' {aka 'long long int'} [-Wsign-compare]
   61 |     if(cur.size()>=k){
      |        ~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:106:8: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    if(j>=cur2.size()){
      |       ~^~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32