Submission #1141908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141908		AtabayRajabli	경주 (Race) (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

const int sz = 2e5 + 5, inf = 1e9 + 7;
int n, m, k, ans, w[sz], len[sz], d[sz], used[sz], par[sz];
vector<array<int, 2>> g[sz];
vector<int> cur, tot;
map<int, int> mp;

void dfs(int v, int p)
{
    w[v] = 1;
    for(auto i : g[v])
    {
        if(i[0] == p) continue;
        dfs(i[0], v);
        w[v] += w[i[0]];                   
    }
}
    
int fnd(int v, int p = 0)
{
    for(auto i : g[v])
    {
        if(i[0] == p || used[i[0]]) continue;
        if(w[i[0]] > w[v] / 2)
        {
            w[v] -= w[i[0]];
            w[i[0]] += w[v];
            return fnd(i[0], v);
        }
    }
    return v;
}

void dist(int v, int p, int cst)
{
    len[v] = len[p] + 1;
    d[v] = d[p] + cst; 
    cur.push_back(v);
    for(auto i : g[v])
    {
        if(i[0] == p || used[i[0]]) continue;
        dist(i[0], v, i[1]);
    }
}

void build(int v)
{
    int c = fnd(v);
    used[c] = 1;
    mp[0] = 0;
    for(auto x : g[c])
    {
        int i = x[0];
        if(used[i]) continue;
        cur.clear();
        dist(i, v, x[1]);
        for(int j : cur)
        {
            if(mp.find(k - d[j]) == mp.end()) continue;
            ans = min(ans, mp[k - d[j]] + len[j]);
        }
        for(int j : cur)
        {
            mp[d[j]] = min(mp[d[j]], len[j]);
        }
    }
    mp.clear();
    for(auto x : g[c])
    {
        if(used[x[0]]) continue;
        build(x[1]);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N, k = K;
    for(int i = 0; i < n - 1; i++)
    {
        int u = h[i][0], v = h[i][1];
        g[u].push_back({v, L[i]});
        g[v].push_back({u, L[i]});
    }
    dfs(1, 1);
    build(1);
    cout << ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:84:17: error: 'h' was not declared in this scope
   84 |         int u = h[i][0], v = h[i][1];
      |                 ^
race.cpp:85:25: error: 'v' was not declared in this scope
   85 |         g[u].push_back({v, L[i]});
      |                         ^
race.cpp:85:23: error: no matching function for call to 'std::vector<std::array<int, 2> >::push_back(<brace-enclosed initializer list>)'
   85 |         g[u].push_back({v, L[i]});
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/11/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::array<int, 2>; _Alloc = std::allocator<std::array<int, 2> >; std::vector<_Tp, _Alloc>::value_type = std::array<int, 2>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<int, 2>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::array<int, 2>; _Alloc = std::allocator<std::array<int, 2> >; std::vector<_Tp, _Alloc>::value_type = std::array<int, 2>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::array<int, 2> >::value_type&&' {aka 'std::array<int, 2>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
race.cpp:91:1: warning: no return statement in function returning non-void [-Wreturn-type]
   91 | }
      | ^