Submission #563424

#	Time	Username	Problem	Language	Result	Execution time	Memory
563424		hibiki	Race (IOI11_race)	C++11	Compilation error	0 ms	0 KiB

race

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

#define pb push_back
#define f first
#define s second

// global
int ans = 1e9, n, k;
vector<pair<int,long long> > v[200005];

// centroid
int sz[200005];
bool visited[200005];

// query & update
map<long long,int> mp;

void query(int nw,int fa,int dep,long long total)
{
    if(mp.count(k - total))
        ans = min(ans, dep + mp[k - total]);
    for(auto go: v[nw])
        if(go.f != fa && !visited[go.f])
            query(go.f, nw, dep + 1, total + go.s);
}

void update(int nw,int fa,int dep, long long total)
{
    if(mp.count(total))
        mp[total] = min(mp[total], dep);
    else
        mp[total] = dep;
    for(auto go: v[nw])
        if(go.f != fa && !visited[go.f])
            query(go.f, nw, dep + 1, total + go.s);
}

int re_size(int nw,int fa)
{
    sz[nw] = 1;
    for(auto go: v[nw])
        if(go.f != fa && !visited[go.f])
            sz[nw] += re_size(go.f,nw);
    return sz[nw];
}

int fi_cen(int nw,int fa,int sum)
{
    for(auto go: v[nw])
        if(go.f != fa && !visited[go.f] && sz[go.f] > sum/2)
            return fi_cen(go.f,nw,sum);
    return nw;
}

void centroid_decomp(int nw)
{
    int cen = fi_cen(nw, -1, re_size(nw, -1));
    visited[cen] = true;

    mp.clear();
    mp.emplace(0, 0);
    for(auto go: v[cen])
    {
        if(!visited[go.f])
        {
            query(go.f, cen, 1, go.s);
            update(go.f, cen, 1, go.s);
        }
    }

    for(auto go: v[cen])
        if(!visited[go.f])
            centroid_decomp(go.f);
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N, k = K;
    for(int i = 0; i < n - 1; i++)
    {
        v[H[i][0]].emplace_back({H[i][1], L[i]});
        v[H[i][1]].emplace_back({H[i][0], L[i]});
    }

    centroid_decomp(0);

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

    return ans;
}

// int a,b;
// int send[200005][2],send2[200005];
// int main()
// {
//     scanf("%d %d",&a,&b);
//     for(int i = 0; i < a - 1; i++)
//         scanf("%d %d %d",&send[i][0],&send[i][1],&send2[i]);
//     printf("%d",best_path(a, b, send, send2));
//     return 0;
// }

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:83:48: error: no matching function for call to 'std::vector<std::pair<int, long long int> >::emplace_back(<brace-enclosed initializer list>)'
   83 |         v[H[i][0]].emplace_back({H[i][1], L[i]});
      |                                                ^
In file included from /usr/include/c++/10/vector:72,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from race.cpp:2:
/usr/include/c++/10/bits/vector.tcc:109:7: note: candidate: 'void std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {}; _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >]'
  109 |       vector<_Tp, _Alloc>::
      |       ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:109:7: note:   candidate expects 0 arguments, 1 provided
race.cpp:84:48: error: no matching function for call to 'std::vector<std::pair<int, long long int> >::emplace_back(<brace-enclosed initializer list>)'
   84 |         v[H[i][1]].emplace_back({H[i][0], L[i]});
      |                                                ^
In file included from /usr/include/c++/10/vector:72,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from race.cpp:2:
/usr/include/c++/10/bits/vector.tcc:109:7: note: candidate: 'void std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {}; _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >]'
  109 |       vector<_Tp, _Alloc>::
      |       ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:109:7: note:   candidate expects 0 arguments, 1 provided