Submission #1270550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270550		tklnic	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define endl '\n'
#define pb push_back
#define rm pop_back
#define f first
#define s second
#define sz size
#define in insert

typedef pair<int, int> p;
typedef long long ll;
const int MAX = 0x3f3f3f3f;
const ll LMAX = 0x3f3f3f3f3f3f3f3f;

int n, k;
ll ans = LMAX;
vector<int> sub;
vector<vector<p>> g;
vector<p> pathSubTree; 
vector<ll> melhor;
vector<ll> flag;
int flagAtual = 0;
bool roots;

void dfsAns(int u, int parent, int sum, int edges){
    if(sum > k) return;

    int rest = k - sum;
    if(flag[rest] == flagAtual){
        ans = min(ans, (ll)edges + melhor[restante]);
    }

    for(auto &[v, w]: g[u]){
        if(v != parent && !roots[v]){
            dfsAns(v, u, sum+w, edges+1);
        }
    }
}

void dfsMelhor(int u, int parent, int sum, int edges){
    if(dist > k) return;

    if(flag[sum] != flagAtual || edges < melhor[sum]){
        melhor[sum] = edges;
        flag[dist] = flagAtual;
    }

    for(auto &[v, w]: g[u]){
        if(v != parent && !roots[v]){
            dfsMelhor(v, u, sum+w, edges+1);
        }
    }
}

int subTree(int u, int parent){
    sub[u] = 1;

    for (auto &[v, w]: g[u])
        if (v != parent && !roots[v])
            sub[u] += subTree(v, u);

    return sub[u];
}

int centroid(int u, int parent, int size){

    for (auto &[v, w]: g[u])
        if (v != parent && sub[v] > size/2 && !roots[v])
            return centroid(v, u, size);

    return u;

}

void algorithm(int root){

    int n = subTree(root, -1);
    int newRoot = centroid(root, -1, n);

    flagAtual++;

    melhor[0] = 0;
    flag[0] = flagAtual;


    for(auto &[v, w]: g[newRoot]){
        if(!roots[v]){
            dfsAns(v, newRoot, w, 1);
            dfsMelhor(v, newRoot, w, 1);
        }
    }

    roots[newRoot] = true;

    for(auto &[v, w]: g[newRoot]){
        if(!roots[v]){
            algorithm(v);
        }
    }

}


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

    n = N;
    k = K;

    g.assign(n, vector<p>());
    sub.resize(n);
    melhor.resize(k+1);
    flag.assign(k+1, 0);
    memset(roots, false, sizeof(roots)); // inicializa o vetor de centroids

    for(int i = 0; i < n-1;i++){ // constroi o grafo
        g[H[i][0]].pb({H[i][1], L[i]});
        g[H[i][1]].pb({H[i][0], L[i]});
    }


    algorithm(0);

    if(ans == LMAX) return -1;
    return ans;

}

Compilation message (stderr)

race.cpp: In function 'void dfsAns(int, int, int, int)':
race.cpp:37:43: error: 'restante' was not declared in this scope
   37 |         ans = min(ans, (ll)edges + melhor[restante]);
      |                                           ^~~~~~~~
race.cpp:41:33: error: invalid types 'bool[std::tuple_element<0, std::pair<int, int> >::type {aka int}]' for array subscript
   41 |         if(v != parent && !roots[v]){
      |                                 ^
race.cpp: In function 'void dfsMelhor(int, int, int, int)':
race.cpp:48:8: error: 'dist' was not declared in this scope
   48 |     if(dist > k) return;
      |        ^~~~
race.cpp:52:14: error: 'dist' was not declared in this scope
   52 |         flag[dist] = flagAtual;
      |              ^~~~
race.cpp:56:33: error: invalid types 'bool[std::tuple_element<0, std::pair<int, int> >::type {aka int}]' for array subscript
   56 |         if(v != parent && !roots[v]){
      |                                 ^
race.cpp: In function 'int subTree(int, int)':
race.cpp:66:34: error: invalid types 'bool[std::tuple_element<0, std::pair<int, int> >::type {aka int}]' for array subscript
   66 |         if (v != parent && !roots[v])
      |                                  ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:75:53: error: invalid types 'bool[std::tuple_element<0, std::pair<int, int> >::type {aka int}]' for array subscript
   75 |         if (v != parent && sub[v] > size/2 && !roots[v])
      |                                                     ^
race.cpp: In function 'void algorithm(int)':
race.cpp:94:18: error: invalid types 'bool[std::tuple_element<0, std::pair<int, int> >::type {aka int}]' for array subscript
   94 |         if(!roots[v]){
      |                  ^
race.cpp:100:10: error: invalid types 'bool[int]' for array subscript
  100 |     roots[newRoot] = true;
      |          ^
race.cpp:103:18: error: invalid types 'bool[std::tuple_element<0, std::pair<int, int> >::type {aka int}]' for array subscript
  103 |         if(!roots[v]){
      |                  ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:120:12: error: cannot convert 'bool' to 'void*'
  120 |     memset(roots, false, sizeof(roots)); // inicializa o vetor de centroids
      |            ^~~~~
      |            |
      |            bool
In file included from /usr/include/features.h:502,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/c++config.h:679,
                 from /usr/include/c++/13/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:33,
                 from race.cpp:1:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:57:1: note:   initializing argument 1 of 'void* memset(void*, int, size_t)'
   57 | __NTH (memset (void *__dest, int __ch, size_t __len))
      | ^~~~~