Submission #1270010

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

race

#include "race.h"

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

#define ii pair<int, int>
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define INF 99999999999999
#define length second

ll n, k, bestSol = INF;
vector<vector<pair<int, ll>>> adj; // node -> {node, length}
vector<pair<int, ll>> smallest; // [lenght] -> {flag, edgeCount}
vector<pair<int, ll>> nodeInfo; // node -> {edgeCount, length}
vi sizes;
vector<bool> wasRoot;
int centroid;

int flag = 0;

void dfs1(int node, int parent, int edgeCount, ll lenSum) {
    nodeInfo[node] = {edgeCount, lenSum};

    if (lenSum > k) return;

    ll s = smallest[k-lenSum].first == flag ? smallest[k-lenSum].second : INF;

    if (k - lenSum >= 0 && s + edgeCount < bestSol) {
        bestSol = smallest[k-lenSum].second + edgeCount;
    }

    for (auto child : adj[node]) if (child.first != parent && !wasRoot[child.first])
        dfs1(child.first, node, edgeCount + 1, lenSum + child.second);
}

void dfs2(int node, int parent) {
    pair<int, ll> info = nodeInfo[node];

    if (info.length > k) return;

    if (smallest[info.length].first != flag || smallest[info.length].second > info.first) {
        smallest[info.length].first = flag;
        smallest[info.length].second = info.first;
    }

    for (auto child : adj[node]) if (child.first != parent && !wasRoot[child.first])
        dfs2(child.first, node);
}

void subtreeSize(int node, int parent) {
    int s = 1;
    for (int i=0; i<adj[node].size(); i++) if (adj[node][i].first != parent && !wasRoot[adj[node][i].first]) {
        subtreeSize(adj[node][i].first, node);
        s += sizes[adj[node][i].first];
    }
    sizes[node] = s;
}

void findCentroid(int node, int parent, int numVert) {
    centroid = node;

    ii max = { -1, -1 }; // val, node;
    bool isCentroid = true;
    for (int i=0; i<adj[node].size(); i++) if (adj[node][i].first != parent && !wasRoot[adj[node][i].first]) {
        if (sizes[adj[node][i].first] > max.first) max = { sizes[adj[node][i].first], adj[node][i].first };
        if (sizes[adj[node][i].first] > numVert / 2) isCentroid = false;
    }
    
    if (!isCentroid) {
        sizes[node] = numVert - sizes[node] + 1;
        findCentroid(max.second, node, numVert);
    }
}

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

    n = N;
    k = K;

    adj = vector<vector<pair<int, ll>>>(n);
    smallest = vector<pair<int, ll>>(1000001, {0, INF});
    for (int i=0; i<n-1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }

    nodeInfo = vector<ii>(n, {-1, -1});

    queue<int> queue;
    wasRoot = vector<bool>(n, false);
    sizes = vi(n, 0);

    queue.push(0);
    while (!queue.empty()) {
        int currRoot = queue.front();

        //sizes = vi(n, 0);
        subtreeSize(currRoot, -1);
        int numVertSubTree = sizes[currRoot];
        findCentroid(currRoot, -1, numVertSubTree);

        currRoot = centroid;
        wasRoot[currRoot] = true;
        smallest[0] = {flag, 0};
        queue.pop();
        for (auto child : adj[currRoot]) if (!wasRoot[child.first]) {
            queue.push(child.first);
            dfs1(child.first, currRoot, 1, child.second);
            dfs2(child.first, currRoot);
        }

        flag++;
    }

    if (bestSol == INF) return -1;
    else return bestSol;
  
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:89:38: error: no match for 'operator=' (operand types are 'std::vector<std::pair<int, long long int> >' and 'std::vector<std::pair<int, int> >')
   89 |     nodeInfo = vector<ii>(n, {-1, -1});
      |                                      ^
In file included from /usr/include/c++/13/vector:72,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53,
                 from race.cpp:3:
/usr/include/c++/13/bits/vector.tcc:210:5: note: candidate: 'constexpr std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >]'
  210 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/vector.tcc:211:42: note:   no known conversion for argument 1 from 'std::vector<std::pair<int, int> >' to 'const std::vector<std::pair<int, long long int> >&'
  211 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/13/vector:66:
/usr/include/c++/13/bits/stl_vector.h:766:7: note: candidate: 'constexpr std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >]'
  766 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:766:26: note:   no known conversion for argument 1 from 'std::vector<std::pair<int, int> >' to 'std::vector<std::pair<int, long long int> >&&'
  766 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:788:7: note: candidate: 'constexpr std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >]'
  788 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:788:46: note:   no known conversion for argument 1 from 'std::vector<std::pair<int, int> >' to 'std::initializer_list<std::pair<int, long long int> >'
  788 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~