| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1037459 | attky | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct Vertice {
int arrivee, poids;
};
struct Path {
int pos, length, depth;
};
int find_centroid(int n, vector<vector<Vertice>> arbre) {
vector<int> nbFils(n, 1);
vector<bool> vu(n, false);
stack<pair<int, int>> pile;
vector<vector<Vertice>> secondArbre = arbre;
pile.push({0, -1});
vu[0] = true;
while(pile.size() > 0) {
int pos = pile.top().first, father = pile.top().second;
if(arbre[pos].size() == 0) {
pile.pop();
if(father != -1) {
nbFils[father] += nbFils[pos];
}
}
else {
if(!vu[arbre[pos].back().arrivee]) {
pile.push({arbre[pos].back().arrivee, pos});
}
vu[arbre[pos].back().arrivee] = true;
arbre[pos].pop_back();
}
}
int maxi = n+1, best = -1;
for(int loop = 0; loop < n; ++loop) {
int sizeMax = n - nbFils[loop];
for(int looping = 0; looping < secondArbre[loop].size(); ++looping) {
sizeMax = max(sizeMax, nbFils[secondArbre[loop][looping].arrivee]);
}
if(sizeMax < maxi) {
maxi = sizeMax;
best = loop;
}
}
return best;
}
vector<int> distMin(1000010, 2e9);
int best_path(int n, int k, vector<vector<int>> h, vector<int> l) {
if(n <= 1) {
return -1;
}
vector<vector<Vertice>> graph(n);
for(int loop = 0; loop < n-1; ++loop) {
graph[h[loop][0]].push_back({h[loop][1], l[loop]});
graph[h[loop][1]].push_back({h[loop][0], l[loop]});
}
int centroid = find_centroid(n, graph);
vector<vector<Vertice>> newGraph = graph;
vector<bool> vu(n, false);
vector<int> allModif;
int mini = 2e9;
for(int loop = 0; loop < newGraph[centroid].size(); ++loop) {
stack<Path> pile;
vector<Path> newPath;
pile.push({graph[centroid][loop].arrivee, graph[centroid][loop].poids, 1});
newPath.push_back(pile.top());
vu[graph[centroid][loop].arrivee] = true;
while(pile.size() > 0) {
Path enCours = pile.top();
if(graph[enCours.pos].size() == 0) {
pile.pop();
}
else {
if(!vu[graph[enCours.pos].back().arrivee]) {
pile.push({graph[enCours.pos].back().arrivee, graph[enCours.pos].back().poids + enCours.length, enCours.depth + 1});
newPath.push_back(pile.top());
}
vu[graph[enCours.pos].back().arrivee] = true;
graph[enCours.pos].pop_back();
}
}
for(int looping = 0; looping < newPath.size(); ++looping) {
if(k - newPath[looping].length >= 0) {
distMin[k] = min(distMin[k], distMin[k - newPath[looping].length] + newPath[looping].depth);
}
}
for(int looping = 0; looping < newPath.size(); ++looping) {
distMin[newPath[looping].length] = min(distMin[newPath[looping].length], newPath[looping].depth);
allModif.push_back(newPath[looping].length);
}
}
mini = distMin[k];
for(int loop = 0; loop < allModif.size(); ++loop) {
distMin[allModif[loop]] = 2e9;
}
distMin[k] = 2e9;
for(int loop = 0; loop < n; ++loop) {
vu[loop] = false;
}
vector<int> value(n, -1);
vu[centroid] = true;
for(int loop = 0; loop < newGraph[centroid].size(); ++loop) {
stack<int> pile;
vector<pair<int, Vertice>> vertice;
int compteur = 1;
pile.push(newGraph[centroid][loop].arrivee);
vu[newGraph[centroid][loop].arrivee] = true;
value[newGraph[centroid][loop].arrivee] = 0;
while(pile.size() > 0) {
int enCours = pile.top();
if(newGraph[enCours].size() == 0) {
pile.pop();
}
else {
if(!vu[newGraph[enCours].back().arrivee]) {
vertice.push_back({value[enCours], {compteur, newGraph[enCours].back().poids}});
value[newGraph[enCours].back().arrivee] = compteur;
compteur++;
pile.push(newGraph[enCours].back().arrivee);
}
vu[newGraph[enCours].back().arrivee] = true;
newGraph[enCours].pop_back();
}
}
vector<vector<int>> littleH(vertice.size(), vector<int>(2));
vector<int> littleL(vertice.size());
for(int loop = 0; loop < vertice.size(); ++loop) {
littleH[loop] = {vertice[loop].first, vertice[loop].second.arrivee};
littleL[loop] = vertice[loop].second.poids;
}
int result = best_path(vertice.size() + 1, k, littleH, littleL);
if(result == -1) {
result = 2e9;
}
mini = min(mini, result);
}
if(mini == 2e9) {
mini = -1;
}
return mini;
}