Submission #798784

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
798784	2023-07-31T04:16:27 Z	OrazB	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KB

factories

#include <iostream>
#include <vector>
#include "factories.h"
using namespace std;

#define ll long long int
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second

const int N = 5e5 + 2;
const ll inf = 1e18;
int rem[N], sub[N], par[N], sp[N][20], lvl[N];
ll w[N], cur[N];
vector<pii> E[N];

void dfs(const vector<pii>& E, int nd, int pr) {
    sub[nd] = 1;
    for (auto i : E[nd]) {
        if (i.ff == pr || rem[i.ff]) continue;
        dfs(E, i.ff, nd);
        sub[nd] += sub[i.ff];
    }
}

int centroid(const vector<pii>& E, int nd, int pr, int sz) {
    for (auto i : E[nd]) {
        if (i.ff == pr || rem[i.ff]) continue;
        if (sub[i.ff] * 2 > sz) return centroid(E, i.ff, nd, sz);
    }
    return nd;
}

void build(const vector<pii>& E, int nd, int pr) {
    int centr = centroid(E, nd, 0, sub[nd]);
    rem[centr] = 1;
    par[centr] = pr;
    for (auto i : E[centr]) {
        if (!rem[i.ff]) {
            dfs(E, i.ff, 0);
            build(E, i.ff, centr);
        }
    }
}

void dfs2(const vector<pii>& E, int nd, int pr) {
    sp[nd][0] = pr;
    for (auto i : E[nd]) {
        if (i.ff == pr) continue;
        lvl[i.ff] = lvl[nd] + 1;
        w[i.ff] = w[nd] + i.ss;
        dfs2(E, i.ff, nd);
    }
}

int LCA(int u, int v) {
    if (lvl[u] < lvl[v]) swap(u, v);
    int diff = lvl[u] - lvl[v];
    for (int i = 19; i >= 0; i--) {
        if (diff & (1 << i)) u = sp[u][i];
    }
    if (u == v) return v;
    for (int i = 19; i >= 0; i--) {
        if (sp[u][i] != sp[v][i]) {
            u = sp[u][i];
            v = sp[v][i];
        }
    }
    return sp[u][0];
}

ll dist(int u, int v) {
    if (u == v) return 0ll;
    return w[u] + w[v] - 2 * w[LCA(u, v)];
}

void Init(int n, int A[], int B[], int D[]) {
    vector<pii> edges;
    for (int i = 0; i < n - 1; i++) {
        A[i]++;
        B[i]++;
        edges.pb({A[i], D[i]});
        edges.pb({B[i], D[i]});
    }
    E[1] = edges; // Assume the tree is rooted at node 1
    dfs(E[1], 1, 0);
    build(E[1], 1, 0);
    dfs2(E[1], 1, 0);
    for (int j = 1; j <= 19; j++) {
        for (int i = 1; i <= n; i++) sp[i][j] = sp[sp[i][j - 1]][j - 1];
    }
    for (int i = 1; i <= n; i++) cur[i] = inf;
}

void remv(int nd) {
    while (nd) {
        cur[nd] = inf;
        nd = par[nd];
    }
}

void paint(int nd) {
    int u = nd;
    while (u) {
        cur[u] = min(cur[u], dist(u, nd));
        u = par[u];
    }
}

ll find(int nd) {
    ll mn = inf;
    int u = nd;
    while (u) {
        mn = min(mn, dist(u, nd) + cur[u]);
        u = par[u];
    }
    return mn;
}

ll Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        X[i]++;
        paint(X[i]);
    }
    ll ans = inf;
    for (int i = 0; i < T; i++) {
        Y[i]++;
        ans = min(ans, find(Y[i]));
    }
    for (int i = 0; i < S; i++) remv(X[i]);
    return ans;
}

Compilation message

factories.cpp: In function 'void dfs(const std::vector<std::pair<int, int> >&, int, int)':
factories.cpp:20:23: error: no matching function for call to 'begin(const std::pair<int, int>&)'
   20 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/bits/range_access.h:36,
                 from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   90 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/10/initializer_list:90:5: note:   template argument deduction/substitution failed:
factories.cpp:20:23: note:   'std::pair<int, int>' is not derived from 'std::initializer_list<_Tp>'
   20 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/bits/range_access.h:51:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&)'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&) [with _Container = const std::pair<int, int>]':
factories.cpp:20:23:   required from here
/usr/include/c++/10/bits/range_access.h:51:50: error: 'const struct std::pair<int, int>' has no member named 'begin'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |                                           ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&)'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::pair<int, int>]':
factories.cpp:20:23:   required from here
/usr/include/c++/10/bits/range_access.h:61:56: error: 'const struct std::pair<int, int>' has no member named 'begin'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |                                                 ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
   90 |     begin(_Tp (&__arr)[_Nm])
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note:   template argument deduction/substitution failed:
factories.cpp:20:23: note:   mismatched types '_Tp [_Nm]' and 'const std::pair<int, int>'
   20 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/bits/range_access.h:107:31: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
  107 |   template<typename _Tp> _Tp* begin(valarray<_Tp>&);
      |                               ^~~~~
/usr/include/c++/10/bits/range_access.h:107:31: note:   template argument deduction/substitution failed:
factories.cpp:20:23: note:   types 'std::valarray<_Tp>' and 'const std::pair<int, int>' have incompatible cv-qualifiers
   20 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/bits/range_access.h:108:37: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
  108 |   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&);
      |                                     ^~~~~
/usr/include/c++/10/bits/range_access.h:108:37: note:   template argument deduction/substitution failed:
factories.cpp:20:23: note:   'const std::pair<int, int>' is not derived from 'const std::valarray<_Tp>'
   20 |     for (auto i : E[nd]) {
      |                       ^
factories.cpp:20:23: error: no matching function for call to 'end(const std::pair<int, int>&)'
In file included from /usr/include/c++/10/bits/range_access.h:36,
                 from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/initializer_list:101:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
  101 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
/usr/include/c++/10/initializer_list:101:5: note:   template argument deduction/substitution failed:
factories.cpp:20:23: note:   'std::pair<int, int>' is not derived from 'std::initializer_list<_Tp>'
   20 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/bits/range_access.h:71:5: note: candidate: 'template<class _Container> decltype (__cont.end()) std::end(_Container&)'
   71 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:71:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(_Container&) [with _Container = const std::pair<int, int>]':
factories.cpp:20:23:   required from here
/usr/include/c++/10/bits/range_access.h:71:48: error: 'const struct std::pair<int, int>' has no member named 'end'
   71 |     end(_Container& __cont) -> decltype(__cont.end())
      |                                         ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:81:5: note: candidate: 'template<class _Container> decltype (__cont.end()) std::end(const _Container&)'
   81 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:81:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(const _Container&) [with _Container = std::pair<int, int>]':
factories.cpp:20:23:   required from here
/usr/include/c++/10/bits/range_access.h:81:54: error: 'const struct std::pair<int, int>' has no member named 'end'
   81 |     end(const _Container& __cont) -> decltype(__cont.end())
      |                                               ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:100:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
  100 |     end(_Tp (&__arr)[_Nm])
      |     ^~~
/usr/include/c++/10/bits/range_access.h:100:5: note:   template argument deduction/substitution failed:
factories.cpp:20:23: note:   mismatched types '_Tp [_Nm]' and 'const std::pair<int, int>'
   20 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/bits/range_access.h:109:31: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
  109 |   template<typename _Tp> _Tp* end(valarray<_Tp>&);
      |                               ^~~
/usr/include/c++/10/bits/range_access.h:109:31: note:   template argument deduction/substitution failed:
factories.cpp:20:23: note:   types 'std::valarray<_Tp>' and 'const std::pair<int, int>' have incompatible cv-qualifiers
   20 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/bits/range_access.h:110:37: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
  110 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&);
      |                                     ^~~
/usr/include/c++/10/bits/range_access.h:110:37: note:   template argument deduction/substitution failed:
factories.cpp:20:23: note:   'const std::pair<int, int>' is not derived from 'const std::valarray<_Tp>'
   20 |     for (auto i : E[nd]) {
      |                       ^
factories.cpp: In function 'int centroid(const std::vector<std::pair<int, int> >&, int, int, int)':
factories.cpp:28:23: error: no matching function for call to 'begin(const std::pair<int, int>&)'
   28 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/bits/range_access.h:36,
                 from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   90 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/10/initializer_list:90:5: note:   template argument deduction/substitution failed:
factories.cpp:28:23: note:   'std::pair<int, int>' is not derived from 'std::initializer_list<_Tp>'
   28 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/bits/range_access.h:51:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&)'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&) [with _Container = const std::pair<int, int>]':
factories.cpp:28:23:   required from here
/usr/include/c++/10/bits/range_access.h:51:50: error: 'const struct std::pair<int, int>' has no member named 'begin'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |                                           ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&)'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::pair<int, int>]':
factories.cpp:28:23:   required from here
/usr/include/c++/10/bits/range_access.h:61:56: error: 'const struct std::pair<int, int>' has no member named 'begin'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |                                                 ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
   90 |     begin(_Tp (&__arr)[_Nm])
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note:   template argument deduction/substitution failed:
factories.cpp:28:23: note:   mismatched types '_Tp [_Nm]' and 'const std::pair<int, int>'
   28 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/bits/range_access.h:107:31: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
  107 |   template<typename _Tp> _Tp* begin(valarray<_Tp>&);
      |                               ^~~~~
/usr/include/c++/10/bits/range_access.h:107:31: note:   template argument deduction/substitution failed:
factories.cpp:28:23: note:   types 'std::valarray<_Tp>' and 'const std::pair<int, int>' have incompatible cv-qualifiers
   28 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/bits/range_access.h:108:37: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
  108 |   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&);
      |                                     ^~~~~
/usr/include/c++/10/bits/range_access.h:108:37: note:   template argument deduction/substitution failed:
factories.cpp:28:23: note:   'const std::pair<int, int>' is not derived from 'const std::valarray<_Tp>'
   28 |     for (auto i : E[nd]) {
      |                       ^
factories.cpp:28:23: error: no matching function for call to 'end(const std::pair<int, int>&)'
In file included from /usr/include/c++/10/bits/range_access.h:36,
                 from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/initializer_list:101:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
  101 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
/usr/include/c++/10/initializer_list:101:5: note:   template argument deduction/substitution failed:
factories.cpp:28:23: note:   'std::pair<int, int>' is not derived from 'std::initializer_list<_Tp>'
   28 |     for (auto i : E[nd]) {
      |                       ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from factories.cpp:1:
/usr/include/c++/10/bits/range_access.h:71:5: note: candidate: 'template<class _Container> decltype (__cont.end()) std::end(_Container&)'
   71 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:71:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(_Container&) [with _Container = const std::pair<int, int>]':
factories.cpp:28:23:   required from here
/usr/include/c++/10/bits/range_access.h:71:48: error: 'const struct std::pair<int, int>' has no member named 'end'
   71 |     end(_Container& __cont) -> decltype(__cont.end())
      |                                         ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:81:5: note: candidate: 'template<class _Container> decltype (__cont.end()) std::end(const _Container&)'
   81 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:81:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(const _Container&) [with _Container = std::pair<int, int>]':
/var/local/lib