oj.uz

Submission #1099611

# Submission time Handle Problem Language Result Execution time Memory
1099611 2024-10-11T20:21:27 Z MrNanama Race (IOI11_race) C++17
0 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;
using ll = long long;

template <typename T> ostream& operator<<(ostream& os, const vector<T>& vec){for (auto itr : vec){os << itr << " ";} return os;}

ll n,k,ans;

vector<vector<pair<ll,ll>>> neigh;
vector<pair<ll,ll>> parent;
vector<vector<pair<ll,ll>>> kids;
vector<ll> depth_d;
vector<ll> depth_r;

vector<set<pair<ll,ll>>> info;

void make_tree(ll v, ll e, ll come_w, ll d_r, ll d_d){
	parent[v] = {e, come_w};
	depth_r[v] = d_r;
	depth_d[v] = d_d;


	for(pair<ll,ll> p:neigh[v]){
		if(p.fi == e){continue;}

		kids[v].pb({p.fi, p.se});
		make_tree(p.fi, v, p.se, d_r+p.se, d_d+1);
	}
}

pair<ll,ll> get_min_dist(set<pair<ll,ll>>& sing_info, ll v){
	auto at = sing_info.lower_bound({v,-LLONG_MAX});

	if(at == sing_info.end() || (*at).fi != v){return {LLONG_MAX,LLONG_MAX};}

	return *at;
}

void dfs(ll v){
	info[v].insert(make_pair(depth_r[v], depth_d[v]));

	for(pair<ll,ll> p:kids[v]){
		dfs(p.fi);
	}

	for(pair<ll,ll> p:kids[v]){
		ll go = p.fi;
		if(info[go].size() > info[v].size()){swap(info[go], info[v]);}

		for(pair<ll,ll> ele:info[go]){
			pair<ll,ll> res = get_min_dist(info[v], k-(depth_r[go]-depth_r[v]));
			if(res.se == LLONG_MAX){continue;}

			ans = min<ll>(ans, res.se);
		}

		for(pair<ll,ll> ele:info[go]){info[v].insert(ele);}
	}
}

//template <size_t N_size>
int best_path(int N_inp, int K_inp, int H_inp[][2], int L_inp[]){
	n = N_inp;
	k = K_inp;
	ans = LLONG_MAX;

	neigh.resize(n);
	parent.resize(n);
	kids.resize(n);

	depth_d.resize(n);
	depth_r.resize(n);
	info.resize(n);

	for(ll i=0; i<n-1; i++){
		ll n1 = H_inp[i][0];
		ll n2 = H_inp[i][1];
		ll w = L_inp[i];

		neigh[n1].pb({n2,w});
		neigh[n2].pb({n1,w});
	}

	make_tree(0, -1, LLONG_MAX, 0, 0);

	dfs(0);

	if(ans == LLONG_MAX){return -1;}
	else{return ans;}
}

Compilation message

race.cpp: In function 'void dfs(ll)':
race.cpp:54:19: warning: variable 'ele' set but not used [-Wunused-but-set-variable]
   54 |   for(pair<ll,ll> ele:info[go]){
      |                   ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -