| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1037945 |
2024-07-29T10:48:37 Z |
attky |
Race (IOI11_race) |
C++17 |
|
6 ms |
12636 KB |
#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) {
if(nbFils[secondArbre[loop][looping].arrivee] > nbFils[loop]) {
continue;
}
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, int h[][2], 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);
vu[centroid] = true;
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) {
if(allModif[loop] >= distMin.size()) {
continue;
}
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();
}
}
int littleH[vertice.size()][2];
int littleL[vertice.size()];
for(int loop = 0; loop < vertice.size(); ++loop) {
littleH[loop][0] = vertice[loop].first;
littleH[loop][1] = 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;
}
Compilation message
race.cpp: In function 'int find_centroid(int, std::vector<std::vector<Vertice> >)':
race.cpp:39:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Vertice>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int looping = 0; looping < secondArbre[loop].size(); ++looping) {
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:71:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Vertice>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int loop = 0; loop < newGraph[centroid].size(); ++loop) {
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:91:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int looping = 0; looping < newPath.size(); ++looping) {
| ~~~~~~~~^~~~~~~~~~~~~~~~
race.cpp:96:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int looping = 0; looping < newPath.size(); ++looping) {
| ~~~~~~~~^~~~~~~~~~~~~~~~
race.cpp:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int loop = 0; loop < allModif.size(); ++loop) {
| ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:103:27: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | if(allModif[loop] >= distMin.size()) {
race.cpp:115:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Vertice>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int loop = 0; loop < newGraph[centroid].size(); ++loop) {
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:140:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, Vertice> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int loop = 0; loop < vertice.size(); ++loop) {
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 5 |
Runtime error |
6 ms |
12636 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 5 |
Runtime error |
6 ms |
12636 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 5 |
Runtime error |
6 ms |
12636 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 5 |
Runtime error |
6 ms |
12636 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
