Submission #1037945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037945		attky	Race (IOI11_race)	C++17	0 / 100	6 ms	12636 KiB

race

#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 (stderr)

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) {
      |                           ~~~~~^~~~~~~~~~~~~~~~

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