oj.uz

Submission #707266

# Submission time Handle Problem Language Result Execution time Memory
707266 2023-03-08T17:42:52 Z Danilo21 Factories (JOI14_factories) C++17
100 / 100
 4563 ms 370644 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24532 KB Output is correct
2 Correct 1568 ms 44136 KB Output is correct
3 Correct 1507 ms 43592 KB Output is correct
4 Correct 1372 ms 44672 KB Output is correct
5 Correct 1639 ms 44608 KB Output is correct
6 Correct 1364 ms 44040 KB Output is correct
7 Correct 1520 ms 43576 KB Output is correct
8 Correct 1429 ms 44716 KB Output is correct
9 Correct 1632 ms 44676 KB Output is correct
10 Correct 1318 ms 44088 KB Output is correct
11 Correct 1505 ms 43828 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24148 KB Output is correct
2 Correct 2180 ms 303656 KB Output is correct
3 Correct 2264 ms 308084 KB Output is correct
4 Correct 1856 ms 301232 KB Output is correct
5 Correct 2383 ms 345040 KB Output is correct
6 Correct 2412 ms 310040 KB Output is correct
7 Correct 2250 ms 98896 KB Output is correct
8 Correct 1701 ms 98644 KB Output is correct
9 Correct 2260 ms 104360 KB Output is correct
10 Correct 2226 ms 100408 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24532 KB Output is correct
2 Correct 1568 ms 44136 KB Output is correct
3 Correct 1507 ms 43592 KB Output is correct
4 Correct 1372 ms 44672 KB Output is correct
5 Correct 1639 ms 44608 KB Output is correct
6 Correct 1364 ms 44040 KB Output is correct
7 Correct 1520 ms 43576 KB Output is correct
8 Correct 1429 ms 44716 KB Output is correct
9 Correct 1632 ms 44676 KB Output is correct
10 Correct 1318 ms 44088 KB Output is correct
11 Correct 1505 ms 43828 KB Output is correct
12 Correct 15 ms 24148 KB Output is correct
13 Correct 2180 ms 303656 KB Output is correct
14 Correct 2264 ms 308084 KB Output is correct
15 Correct 1856 ms 301232 KB Output is correct
16 Correct 2383 ms 345040 KB Output is correct
17 Correct 2412 ms 310040 KB Output is correct
18 Correct 2250 ms 98896 KB Output is correct
19 Correct 1701 ms 98644 KB Output is correct
20 Correct 2260 ms 104360 KB Output is correct
21 Correct 2226 ms 100408 KB Output is correct
22 Correct 3622 ms 335376 KB Output is correct
23 Correct 3057 ms 335152 KB Output is correct
24 Correct 4220 ms 340432 KB Output is correct
25 Correct 4164 ms 338116 KB Output is correct
26 Correct 4563 ms 308572 KB Output is correct
27 Correct 4505 ms 370644 KB Output is correct
28 Correct 3310 ms 337908 KB Output is correct
29 Correct 4100 ms 315780 KB Output is correct
30 Correct 4289 ms 315072 KB Output is correct
31 Correct 4017 ms 315928 KB Output is correct
32 Correct 2666 ms 128264 KB Output is correct
33 Correct 2080 ms 123108 KB Output is correct
34 Correct 2463 ms 96884 KB Output is correct
35 Correct 2341 ms 96800 KB Output is correct
36 Correct 2618 ms 97612 KB Output is correct
37 Correct 2579 ms 97628 KB Output is correct