Submission #1134107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134107		Nelt	Factories (JOI14_factories)	C++20	Compilation error	0 ms	0 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 5e5 + 5, lg = 20;
vector<pair<ll, ll>> g[N];
ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
bool used[N];
void dfs(ll v, ll par = 0)
{
    up[0][v] = par;
    for (ll i = 1; i < lg; i++) up[i][v] = up[i - 1][up[i - 1][v]];
    for (auto [to, w] : g[v])
        if (to != par) depth[to] = depth[v] + 1, dis[to] = dis[v] + w, dfs(to, v);
}
ll lca(ll a, ll b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (ll bit = lg - 1; bit >= 0; bit--) if (depth[a] - (1 << bit) >= depth[b]) a = up[bit][a];
    if (a == b) return a;
    for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][a] != up[bit][b]) a = up[bit][a], b = up[bit][b];
    return up[0][a];
}
ll dist(ll a, ll b)
{
    return dis[a] + dis[b] - dis[lca(a, b)] * 2;
}
void init(ll v, ll par = -1)
{
    sub[v] = 1;
    for (auto [to, w] : g[v])
        if (to != par and !used[to]) init(to, v), sub[v] += sub[to];
}
ll findcentroid(ll v, ll par = -1, ll sz = 0)
{
    for (auto [to, w] : g[v])
        if (to != par and !used[to] and sub[to] > sz / 2) return findcentroid(to, v, sz); 
    return v;
}
ll decompose(ll v)
{
    init(v);
    ll cent = findcentroid(v, -1, sub[v]);
    used[cent] = 1;
    for (auto [to, w] : g[cent])
        if (!used[to])
            p[decompose(to)] = cent;
    return cent;
}
void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for (ll i = 0; i < n - 1; i++) g[A[i]].push_back(make_pair(B[i], D[i])), g[B[i]].push_back(make_pair(A[i], D[i]));
    dfs(0);
    for (ll i = 0; i < n; i++) best[i] = 1e18, p[i] = -1;
    decompose(0);
}

long long Query(int S, int X[], int T, int Y[])
{
    for (ll i = 0; i < S; i++)
    {
        ll v = X[i];
        while (v >= 0)
        {
            best[v] = min(best[v], dist(v, X[i]));
            v = p[v];
        }
    }
    ll ans = 9e18;
    for (ll i = 0; i < T; i++)
    {
        ll v = Y[i];
        while (v >= 0)
        {
            ans = min(ans, best[v] + dist(v, Y[i]));
            v = p[v];
        }
    }
    for (ll i = 0; i < S; i++)
    {
        ll v = X[i];
        while (v >= 0)
        {
            best[v] = 1e18;
            v = p[v];
        }
    }
    return ans;
}
#include "factories.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 5e5 + 5, lg = 20;
vector<pair<ll, ll>> g[N];
ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
bool used[N];
void dfs(ll v, ll par = 0)
{
    up[0][v] = par;
    for (ll i = 1; i < lg; i++) up[i][v] = up[i - 1][up[i - 1][v]];
    for (auto [to, w] : g[v])
        if (to != par) depth[to] = depth[v] + 1, dis[to] = dis[v] + w, dfs(to, v);
}
ll lca(ll a, ll b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (ll bit = lg - 1; bit >= 0; bit--) if (depth[a] - (1 << bit) >= depth[b]) a = up[bit][a];
    if (a == b) return a;
    for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][a] != up[bit][b]) a = up[bit][a], b = up[bit][b];
    return up[0][a];
}
ll dist(ll a, ll b)
{
    return dis[a] + dis[b] - dis[lca(a, b)] * 2;
}
void init(ll v, ll par = -1)
{
    sub[v] = 1;
    for (auto [to, w] : g[v])
        if (to != par and !used[to]) init(to, v), sub[v] += sub[to];
}
ll findcentroid(ll v, ll par = -1, ll sz = 0)
{
    for (auto [to, w] : g[v])
        if (to != par and !used[to] and sub[to] > sz / 2) return findcentroid(to, v, sz); 
    return v;
}
ll decompose(ll v)
{
    init(v);
    ll cent = findcentroid(v, -1, sub[v]);
    used[cent] = 1;
    for (auto [to, w] : g[cent])
        if (!used[to])
            p[decompose(to)] = cent;
    return cent;
}
void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for (ll i = 0; i < n - 1; i++) g[A[i]].push_back(make_pair(B[i], D[i])), g[B[i]].push_back(make_pair(A[i], D[i]));
    dfs(0);
    for (ll i = 0; i < n; i++) best[i] = 1e18, p[i] = -1;
    decompose(0);
}

long long Query(int S, int X[], int T, int Y[])
{
    for (ll i = 0; i < S; i++)
    {
        ll v = X[i];
        while (v >= 0)
        {
            best[v] = min(best[v], dist(v, X[i]));
            v = p[v];
        }
    }
    ll ans = 9e18;
    for (ll i = 0; i < T; i++)
    {
        ll v = Y[i];
        while (v >= 0)
        {
            ans = min(ans, best[v] + dist(v, Y[i]));
            v = p[v];
        }
    }
    for (ll i = 0; i < S; i++)
    {
        ll v = X[i];
        while (v >= 0)
        {
            best[v] = 1e18;
            v = p[v];
        }
    }
    return ans;
}

Compilation message (stderr)

factories.cpp:110:12: error: redefinition of 'std::mt19937_64 rng'
  110 | mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
      |            ^~~
factories.cpp:11:12: note: 'std::mt19937_64 rng' previously declared here
   11 | mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
      |            ^~~
factories.cpp:113:10: error: redefinition of 'const long long int N'
  113 | const ll N = 5e5 + 5, lg = 20;
      |          ^
factories.cpp:14:10: note: 'const long long int N' previously defined here
   14 | const ll N = 5e5 + 5, lg = 20;
      |          ^
factories.cpp:113:23: error: redefinition of 'const long long int lg'
  113 | const ll N = 5e5 + 5, lg = 20;
      |                       ^~
factories.cpp:14:23: note: 'const long long int lg' previously defined here
   14 | const ll N = 5e5 + 5, lg = 20;
      |                       ^~
factories.cpp:114:22: error: redefinition of 'std::vector<std::pair<long long int, long long int> > g [500005]'
  114 | vector<pair<ll, ll>> g[N];
      |                      ^
factories.cpp:15:22: note: 'std::vector<std::pair<long long int, long long int> > g [500005]' previously declared here
   15 | vector<pair<ll, ll>> g[N];
      |                      ^
factories.cpp:115:4: error: redefinition of 'long long int sub [500005]'
  115 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |    ^~~
factories.cpp:16:4: note: 'long long int sub [500005]' previously declared here
   16 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |    ^~~
factories.cpp:115:12: error: redefinition of 'long long int p [500005]'
  115 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |            ^
factories.cpp:16:12: note: 'long long int p [500005]' previously declared here
   16 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |            ^
factories.cpp:115:18: error: redefinition of 'long long int n'
  115 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |                  ^
factories.cpp:16:18: note: 'long long int n' previously declared here
   16 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |                  ^
factories.cpp:115:21: error: redefinition of 'long long int up [20][500005]'
  115 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |                     ^~
factories.cpp:16:21: note: 'long long int up [20][500005]' previously declared here
   16 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |                     ^~
factories.cpp:115:32: error: redefinition of 'long long int depth [500005]'
  115 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |                                ^~~~~
factories.cpp:16:32: note: 'long long int depth [500005]' previously declared here
   16 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |                                ^~~~~
factories.cpp:115:42: error: redefinition of 'long long int dis [500005]'
  115 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |                                          ^~~
factories.cpp:16:42: note: 'long long int dis [500005]' previously declared here
   16 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |                                          ^~~
factories.cpp:115:50: error: redefinition of 'long long int best [500005]'
  115 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |                                                  ^~~~
factories.cpp:16:50: note: 'long long int best [500005]' previously declared here
   16 | ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
      |                                                  ^~~~
factories.cpp:116:6: error: redefinition of 'bool used [500005]'
  116 | bool used[N];
      |      ^~~~
factories.cpp:17:6: note: 'bool used [500005]' previously declared here
   17 | bool used[N];
      |      ^~~~
factories.cpp:117:6: error: redefinition of 'void dfs(long long int, long long int)'
  117 | void dfs(ll v, ll par = 0)
      |      ^~~
factories.cpp:18:6: note: 'void dfs(long long int, long long int)' previously defined here
   18 | void dfs(ll v, ll par = 0)
      |      ^~~
factories.cpp:124:4: error: redefinition of 'long long int lca(long long int, long long int)'
  124 | ll lca(ll a, ll b)
      |    ^~~
factories.cpp:25:4: note: 'long long int lca(long long int, long long int)' previously defined here
   25 | ll lca(ll a, ll b)
      |    ^~~
factories.cpp:132:4: error: redefinition of 'long long int dist(long long int, long long int)'
  132 | ll dist(ll a, ll b)
      |    ^~~~
factories.cpp:33:4: note: 'long long int dist(long long int, long long int)' previously defined here
   33 | ll dist(ll a, ll b)
      |    ^~~~
factories.cpp:136:6: error: redefinition of 'void init(long long int, long long int)'
  136 | void init(ll v, ll par = -1)
      |      ^~~~
factories.cpp:37:6: note: 'void init(long long int, long long int)' previously defined here
   37 | void init(ll v, ll par = -1)
      |      ^~~~
factories.cpp:142:4: error: redefinition of 'long long int findcentroid(long long int, long long int, long long int)'
  142 | ll findcentroid(ll v, ll par = -1, ll sz = 0)
      |    ^~~~~~~~~~~~
factories.cpp:43:4: note: 'long long int findcentroid(long long int, long long int, long long int)' previously defined here
   43 | ll findcentroid(ll v, ll par = -1, ll sz = 0)
      |    ^~~~~~~~~~~~
factories.cpp:148:4: error: redefinition of 'long long int decompose(long long int)'
  148 | ll decompose(ll v)
      |    ^~~~~~~~~
factories.cpp:49:4: note: 'long long int decompose(long long int)' previously defined here
   49 | ll decompose(ll v)
      |    ^~~~~~~~~
factories.cpp:158:6: error: redefinition of 'void Init(int, int*, int*, int*)'
  158 | void Init(int N, int A[], int B[], int D[])
      |      ^~~~
factories.cpp:59:6: note: 'void Init(int, int*, int*, int*)' previously defined here
   59 | void Init(int N, int A[], int B[], int D[])
      |      ^~~~
factories.cpp:167:11: error: redefinition of 'long long int Query(int, int*, int, int*)'
  167 | long long Query(int S, int X[], int T, int Y[])
      |           ^~~~~
factories.cpp:68:11: note: 'long long int Query(int, int*, int, int*)' previously defined here
   68 | long long Query(int S, int X[], int T, int Y[])
      |           ^~~~~