oj.uz

Submission #990501

# Submission time Handle Problem Language Result Execution time Memory
990501 2024-05-30T14:54:29 Z mateuszwes Race (IOI11_race) C++17
0 / 100
 2 ms 12636 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
#define ull unsigned ll

#include "race.h"

using namespace std;

constexpr int debug = 1;
constexpr int M = 2e5+7;
constexpr int D = 1e6+7;

int tree_size[M];
int total_size;
bool was_centroid[M];
ll Kek;
ll mini = 1e9+7;
ll closest[D];
queue<int> changes; 		//komorki z closest do wyzerowania

vector<pair<ll,ll>> adj[M];

inline void addEdge(ll a, ll b, ll val){
	adj[a].pb({b, val});
	adj[b].pb({a, val});
}

void set_size(int s, int p){
	tree_size[s] = 1;
	for(auto k: adj[s]){
		if(k.F == p || was_centroid[k.F]) continue;
		set_size(k.F, s);
		tree_size[s] += tree_size[k.F];
	}
}

int find_centroid(int s, int p){
	for(auto k: adj[s]){
		if(was_centroid[k.F]) continue;
		else if(k.F == p){
			if(total_size-tree_size[s] > total_size/2) return find_centroid(k.F, s);
		}
		else if(tree_size[k.F] > total_size/2){
			return find_centroid(k.F, s);
		}
	}
	return s;
}

void DFS1(int s, int p, ll dist_v, ll dist_e){		//sprawdza, ile ma odpowiadajacy wierzcholek
	if(dist_e == Kek) mini = min(mini, dist_v+1);
	if((dist_e < Kek) && (closest[Kek-dist_e])) mini = min(mini, closest[Kek-dist_e]+dist_v);

	for(auto k: adj[s]){
		if(was_centroid[s] || k.F == p) continue;
		DFS1(k.F, s, dist_v+1, dist_e+k.S);
	}
}

void DFS2(int s, int p, ll dist_v, ll dist_e){	//aktualizacje wierzcholkow w danych odleglosciach
	if(dist_e <= Kek){
		if(closest[dist_e] == 0 || closest[dist_e] > dist_v){
			changes.push(dist_e);
			closest[dist_e] = dist_v;
		}
	}
	
	for(auto k: adj[s]){
		if(was_centroid[s] || k.F == p) continue;
		DFS2(k.F, s, dist_v+1, dist_e+k.S);
	}
}

void centroid_decomposition(int x){
	set_size(x, x);
	total_size = tree_size[x];
	int cen = find_centroid(x, x);

	//robi cos na centroidzie

	for(auto k: adj[cen]){
		if(!was_centroid[k.F]){
			DFS1(k.F, cen, 1, k.S);
			DFS2(k.F, cen, 1, k.S);
		}
	}

	while(!changes.empty()){
		closest[changes.front()] = 0;
		changes.pop();
	}

	was_centroid[cen] = 1;

	for(auto k: adj[cen]){
		if(!was_centroid[k.F]) centroid_decomposition(k.F);
	}
	
}

int best_path(int N, int K, int H[][2], int L[]){
  	Kek = K;

  	for(int i = 0; i < N-1; i++){
  		addEdge(H[i][0], H[i][1], L[i]);
  	}

  	centroid_decomposition(0);
  	if(mini == 1e9+7) mini = -1;

  	return mini;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Incorrect 2 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Incorrect 2 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Incorrect 2 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Incorrect 2 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -