Submission #426013

#	Time	Username	Problem	Language	Result	Execution time	Memory
426013		Mounir	Race (IOI11_race)	C++14	100 / 100	665 ms	103724 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;

const int N_NOEUDS = 1e6;

struct SousArbre {
	map<int, int> profMin;
};

vector<SousArbre> arbre;
bool vu[N_NOEUDS];
int prof[N_NOEUDS], distRacine[N_NOEUDS];
vector<pii> voisins[N_NOEUDS];

int ans = N_NOEUDS, k;

int fusion(int pere, int fils, int noeud){
	if (sz(arbre[pere].profMin) < sz(arbre[fils].profMin))
		return fusion(fils, pere, noeud);

	for (pii couple : arbre[fils].profMin){
		int cible = k + 2 * distRacine[noeud] - couple.first;
		if (arbre[pere].profMin.count(cible) == 1)
			chmin(ans, couple.second + arbre[pere].profMin[cible] - 2 * prof[noeud]);
	}

	for (pii couple : arbre[fils].profMin){
		if (arbre[pere].profMin.count(couple.first) == 1)
			chmin(arbre[pere].profMin[couple.first], couple.second);
		else
			arbre[pere].profMin[couple.first] = couple.second;
	}

	return pere;
}

int parcours(int noeud, int etage, int dRoot){
	vu[noeud] = true;
	prof[noeud] = etage;
	distRacine[noeud] = dRoot;

	int ind = sz(arbre);
	map<int, int> p; p[distRacine[noeud]] = prof[noeud];
	arbre.pb({p});

	for (pii sortant : voisins[noeud]){
		int enfant = sortant.first, distSup = sortant.second;
		if (vu[enfant]) continue;
		ind = fusion(ind, parcours(enfant, etage + 1, dRoot + distSup), noeud);
	}

	return ind;
}

int best_path(int N, int K, int H[][2], int L[]){
	k = K;
	for (int ind = 0; ind < N - 1; ++ind){
		int poids = L[ind], noeud = H[ind][0], voisin = H[ind][1];
		voisins[noeud].pb({voisin, poids});
		voisins[voisin].pb({noeud, poids});
	}

	int racine = parcours(0, 0, 0);
	/*for (pii couple : arbre[racine].profMin)
		cout << "paire " << couple.first << " " << couple.second << endl;*/
	if (ans == N_NOEUDS) ans = -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:68:6: warning: unused variable 'racine' [-Wunused-variable]
   68 |  int racine = parcours(0, 0, 0);
      |      ^~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57