oj.uz

Submission #1114324

# Submission time Handle Problem Language Result Execution time Memory
1114324 2024-11-18T14:34:23 Z tintingyn21 Factories (JOI14_factories) C++17
100 / 100
 4569 ms 243596 KB 

// author : daohuyenchi



#ifdef LOCAL
    #include "D:\C++ Submit\debug.h"
#else
    #define debug(...)
#endif



#include <bits/stdc++.h>

using namespace std;

#define ull unsigned long long
#define db double
#define i32 int32_t  
#define i64 int64_t 
#define ll long long
// 
#define fi first
#define se second


//                                      #define int long long    // consider carefully


//
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll> 
#define PAIR make_pair 
//                                      TIME IS LIMITED ...  
#define  rep(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define repd(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define repv(v, H) for(auto &v: H)
//                                      REFLECT ON THE PAST ...
#define RESET(c, x) memset(c, x, sizeof(c))
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1LL)
#define ONBIT(mask, i) ((mask) | (1LL << (i)))
#define OFFBIT(mask, i) ((mask) &~ (1LL << (i)))
#define COUNTBIT __builtin_popcountll
//                                      30 / 1 / 2024 ? love is zero... start from zero 
#define vi vector <int>
#define vll vector <ll>
#define lwb lower_bound
#define upb upper_bound
#define all(v) (v).begin(), (v).end()
#define special(H) (H).resize(distance(H.begin(), unique(all(H))))
//                                      
#define sp ' ' 
#define nl '\n'
#define EL {cerr << '\n';}
#define yes "YES"
#define no "NO"
#define Log2(n) (63 - __builtin_clzll(n))
#define left __left__
#define right __right__ 
#define lps(id) ((id) << 1)
#define rps(id) ((id) << 1 | 1)

//____________________________________________________________________


template <class X, class Y> bool maximize(X &a, const Y &b) {
    if(a < b) return a = b, true;
    return false;
}

template <class X, class Y> bool minimize(X &a, const Y &b) {
    if(a > b) return a = b, true;
    return false;
}

template <class... T>
void print(T&&... n) {
    using exp = int[];
    exp{0, (cerr << n << sp, 0)...};
    cerr << nl;
}

template <class T, class... C>
void assign(int n, T v, C&&... a) {
    using e = int[];
    e{(a.assign(n, v), 0)...};
}

template <class... C>
void resize(int n, C&&... a) {
    using e = int[];
    e{(a.resize(n), 0)...};
}

template <class T>
using vector2d = vector<vector<T>>;
template <class T>
using vector3d = vector<vector2d<T>>;

template <class T> int ssize(T &a) { return (int) a.size(); }


//____________________________________________________________________


mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());

const int MOD      = 1000000007;
// const int MOD[2] = {1000000009, 998244353};

template<class X> void modmize(X &x, int cur_Mod = MOD) {
    if(x >= cur_Mod) x -= cur_Mod;
    if(x < 0) x += cur_Mod;
}

const long long oo = 1e18 + 7;
const long long LINF = 1e18 + 7;
const int IINF      = 2e9;
const int nmax     = 1e6 + 10;
const int MAX      = 2e5;
const int base     = 311;
const db eps       = 1e-6;
const int block    = 500;
static const double PI = acos(-1.0);

//____________________________________________________________________


int n, Q;
int a[nmax], b[nmax], wei[nmax];
int S, T, X[nmax], Y[nmax];
vector <pii> G[nmax];
int par[nmax][22];


struct LCA_Euler {
    int timer = 0;
    int ein[nmax], tour[nmax * 2], dep[nmax];
 
    int min_node(int u, int v) {
        return dep[u] <= dep[v] ? u : v;
    }
 
    void dfs(int u, int p) {
        ein[u] = ++timer;
        tour[timer] = u;
        dep[u] = dep[p] + 1;
        repv (e, G[u]) {
            int v = e.se;
            if (v == p) continue;
            dfs(v, u);
            tour[++timer] = u;
        }
    }
 
    int r_lca[nmax][22];
    void build_lca() {
 
        dfs(1, 0);
 
        rep (i, 1, timer) {
            r_lca[i][0] = tour[i];
        }
 
        rep (k, 1, 20) {
            for (int i = 1; i + (1 << k) - 1 <= timer; ++i) {
                r_lca[i][k] = min_node(r_lca[i][k - 1], r_lca[i + (1 << (k - 1))][k - 1]);
            }
        }
    }
 
    int get_lca(int u, int v) {
        int l = ein[u];
        int r = ein[v];
        if (l > r) swap (l, r);
        int k = Log2(r - l + 1);
        return min_node(r_lca[l][k], r_lca[r - (1 << k) + 1][k]);
    }
 
} lca;
 
ll pf[nmax];
void dfs(int u, int p) {
    repv (e, G[u]) {
        int v = e.se;
        int w = e.fi;
        if (v == p) continue;
        pf[v] = pf[u] + w;
        dfs(v, u);
    }
}
 
ll get_dist(int u, int v) {
    int anc = lca.get_lca(u, v);
    return pf[u] + pf[v] - 2ll * pf[anc];
}


int child[nmax];
bool del[nmax];
int dfs_sz(int u, int p) {
    child[u] = 1;
    repv (e, G[u]) {
        int v = e.se;
        int w = e.fi;
        if (del[v] || v == p) continue;
        child[u] += dfs_sz(v, u);
    }
    return child[u];
}

int Find_cent(int u, int p, int tar) {
    repv (e, G[u]) {
        int v = e.se;
        if (v == p || del[v] || child[v] <= tar) continue;
        return Find_cent(v, u, tar);
    }
    return u ;
}

void solve(int u, int pa) {

    int root = Find_cent(u, 0, dfs_sz(u, 0) / 2);
    del[root] = 1;
    par[root][0] = pa;

    repv (e, G[root]) {
        int v = e.se;
        if (del[v]) continue;
        solve(v, root);
    }
}

ll d[nmax];
void Init(int n, int a[], int b[], int wei[]) {

    rep (i, 0, n - 2) {
        ++a[i];
        ++b[i];
        G[a[i]].push_back({wei[i], b[i]});
        G[b[i]].push_back({wei[i], a[i]});
    }
    
    lca.build_lca();
    dfs(1, 0);
    solve(1, 0);

    rep (i, 1, n) {
        d[i] = LINF;
    }

}


void upd(int u) {
    int u0 = u;
    while (u != 0) {
        // debug(u);
        minimize(d[u], get_dist(u, u0));
        u = par[u][0];
    }   
}

void upd_init(int u) {
    while (u != 0) {
        d[u] = LINF;
        u = par[u][0];
    }
}
 
ll get(int u) {
    int u0 = u;
    ll ans = d[u];
    while (u != 0) {
        minimize(ans, d[u] + get_dist(u, u0));
        u = par[u][0];
    }
    return ans;
}

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

    rep (i, 0, S - 1) ++X[i];
    rep (i, 0, T - 1) ++Y[i];

    rep (i, 0, S - 1) {
        upd(X[i]);
    }

    ll ans = LINF;
    rep (i, 0, T - 1) {
        minimize(ans, get(Y[i]));
    }

    rep (i, 0, S - 1) {
        upd_init(X[i]);
    }

    return ans;

}

Compilation message

factories.cpp: In function 'int dfs_sz(int, int)':
factories.cpp:210:13: warning: unused variable 'w' [-Wunused-variable]
  210 |         int w = e.fi;
      |             ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 53840 KB Output is correct
2 Correct 373 ms 47792 KB Output is correct
3 Correct 514 ms 42704 KB Output is correct
4 Correct 476 ms 46904 KB Output is correct
5 Correct 543 ms 49520 KB Output is correct
6 Correct 190 ms 47688 KB Output is correct
7 Correct 492 ms 47808 KB Output is correct
8 Correct 510 ms 47688 KB Output is correct
9 Correct 575 ms 45144 KB Output is correct
10 Correct 182 ms 49224 KB Output is correct
11 Correct 504 ms 47808 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47696 KB Output is correct
2 Correct 1636 ms 212860 KB Output is correct
3 Correct 1963 ms 214856 KB Output is correct
4 Correct 685 ms 218776 KB Output is correct
5 Correct 3109 ms 243596 KB Output is correct
6 Correct 2298 ms 222380 KB Output is correct
7 Correct 1351 ms 88076 KB Output is correct
8 Correct 368 ms 81596 KB Output is correct
9 Correct 1536 ms 88056 KB Output is correct
10 Correct 1342 ms 88488 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 53840 KB Output is correct
2 Correct 373 ms 47792 KB Output is correct
3 Correct 514 ms 42704 KB Output is correct
4 Correct 476 ms 46904 KB Output is correct
5 Correct 543 ms 49520 KB Output is correct
6 Correct 190 ms 47688 KB Output is correct
7 Correct 492 ms 47808 KB Output is correct
8 Correct 510 ms 47688 KB Output is correct
9 Correct 575 ms 45144 KB Output is correct
10 Correct 182 ms 49224 KB Output is correct
11 Correct 504 ms 47808 KB Output is correct
12 Correct 9 ms 47696 KB Output is correct
13 Correct 1636 ms 212860 KB Output is correct
14 Correct 1963 ms 214856 KB Output is correct
15 Correct 685 ms 218776 KB Output is correct
16 Correct 3109 ms 243596 KB Output is correct
17 Correct 2298 ms 222380 KB Output is correct
18 Correct 1351 ms 88076 KB Output is correct
19 Correct 368 ms 81596 KB Output is correct
20 Correct 1536 ms 88056 KB Output is correct
21 Correct 1342 ms 88488 KB Output is correct
22 Correct 2557 ms 217264 KB Output is correct
23 Correct 2405 ms 218316 KB Output is correct
24 Correct 3448 ms 220980 KB Output is correct
25 Correct 3468 ms 222832 KB Output is correct
26 Correct 3142 ms 221220 KB Output is correct
27 Correct 4569 ms 237004 KB Output is correct
28 Correct 859 ms 218960 KB Output is correct
29 Correct 3123 ms 218980 KB Output is correct
30 Correct 3296 ms 219196 KB Output is correct
31 Correct 3273 ms 220912 KB Output is correct
32 Correct 1462 ms 94696 KB Output is correct
33 Correct 353 ms 88196 KB Output is correct
34 Correct 915 ms 86856 KB Output is correct
35 Correct 1020 ms 86784 KB Output is correct
36 Correct 1433 ms 86336 KB Output is correct
37 Correct 1329 ms 86344 KB Output is correct