Submission #707266

#	Time	Username	Problem	Language	Result	Execution time	Memory
707266		Danilo21	Factories (JOI14_factories)	C++17	100 / 100	4563 ms	370644 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "Yes" << en
#define no cout << "No" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

class Sparse{

    int n;
    vector<ll> a;
    vector<vector<int> > lookup;

public:
    Sparse(){}
    Sparse(const vector<ll>& A){ Assign(A); }

    void Assign(const vector<ll>& A){
        n = A.size();
        a = A;
        lookup.assign(n, vector<int>(lg(n)+1, -1));

        for (int i = 0; i < n; i++)
            lookup[i][0] = i;
        for (int d = 1; d <= lg(n); d++){
            for (int i = 0; i < n; i++){
                if (i + (1 << (d-1)) < n){
                    int x = lookup[i][d-1], y = lookup[i+(1<<(d-1))][d-1];
                    lookup[i][d] = (!~y || a[x] < a[y] ? x : y);
                }
            }
        }
    }

    int query(int l, int r) const {
        int d = highpow(r-l+1);
        int x = lookup[l][lg(d)], y = lookup[r-d+1][lg(d)];
        return (a[x] < a[y] ? x : y);
    }
};

const ll LINF = 1e18;
const int mxN = 1e6+10, INF = 2e9;
ll n, dist[mxN], in[mxN], out[mxN];
vector<array<ll, 2> > g[mxN];
vector<ll> e, d;
Sparse E;

int Lca(int u, int v){

    if (in[u] > in[v]) swap(u, v);
    return e[E.query(in[u], out[v])];
}

ll Dist(int u, int v){

    int s = Lca(u, v);
    return dist[u] + dist[v] - 2*dist[s];
}

void Euler(int s = 0, int p = -1, ll dep = 0){

    dist[s] = dep;
    in[s] = e.size();
    e.pb(s); d.pb(dep);
    for (auto [u, w] : g[s]){
        if (u^p){
            Euler(u, s, dep+w);
            e.pb(s); d.pb(dep);
        }
    }
    out[s] = e.size();
    e.pb(s); d.pb(dep);
}

void Init(int N, int A[], int B[], int D[]){

    n = N;
    for (int i = 0; i < n-1; i++){
        g[A[i]].pb({B[i], D[i]});
        g[B[i]].pb({A[i], D[i]});
    }
    Euler();
    E.Assign(d);
}

void Build(int N, int A[], vector<array<int, 2> >& e, vector<ll>& d){

    for (int i = 0; i < N; i++){
        e.pb({in[A[i]], A[i]});
        e.pb({out[A[i]], A[i]});
    }
    sort(all(e));
    for (auto [i, s] : e) d.pb(dist[s]);
}

int BSL(int x, const vector<array<int, 2> >& a){

    int l = 0, r = a.size()-1, ans = a.size();
    while (l <= r){
        int k = (l + r + 1)>>1;
        if (a[k][0] >= x){
            ans = k;
            r = k - 1;
        }
        else l = k + 1;
    }
    return ans;
}

int BSR(int x, const vector<array<int, 2> >& a){

    int l = 0, r = a.size()-1, ans = -1;
    while (l <= r){
        int k = (l + r + 1)>>1;
        if (a[k][0] <= x){
            ans = k;
            l = k + 1;
        }
        else r = k - 1;
    }
    return ans;
}

long long Query(int S, int X[], int T, int Y[]){

    vector<array<int, 2> > eX, eY;
    vector<ll> dX, dY;
    Build(S, X, eX, dX);
    Build(T, Y, eY, dY);
    Sparse sX(dX), sY(dY);
    vector<int> a;
    for (auto [i, s] : eX) a.pb(i);
    for (auto [i, s] : eY) a.pb(i);
    sort(all(a));
    vector<int> A;
    for (int i = 0; i < a.size()-1; i++)
        A.pb(e[E.query(a[i], a[i+1])]);
    ll ans = LINF;
    for (int s : A){
        int i = BSL(in[s], eX), j = BSR(out[s], eX);
        if (i > j) continue;
        int u = eX[sX.query(i, j)][1];
        i = BSL(in[s], eY); j = BSR(out[s], eY);
        if (i > j) continue;
        int v = eY[sY.query(i, j)][1];
        smin(ans, Dist(u, v));
    }
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void Build(int, int*, std::vector<std::array<int, 2> >&, std::vector<long long int>&)':
factories.cpp:115:22: warning: narrowing conversion of 'in[(*(A + ((sizetype)(((long unsigned int)i) * 4))))]' from 'long long int' to 'int' [-Wnarrowing]
  115 |         e.pb({in[A[i]], A[i]});
      |               ~~~~~~~^
factories.cpp:116:23: warning: narrowing conversion of 'out[(*(A + ((sizetype)(((long unsigned int)i) * 4))))]' from 'long long int' to 'int' [-Wnarrowing]
  116 |         e.pb({out[A[i]], A[i]});
      |               ~~~~~~~~^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:162:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for (int i = 0; i < a.size()-1; i++)
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67