oj.uz

Submission #1114300

# Submission time Handle Problem Language Result Execution time Memory
1114300 2024-11-18T13:44:59 Z tintingyn21 Factories (JOI14_factories) C++17
100 / 100
 2729 ms 240540 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);

//____________________________________________________________________


vector <pii> G[nmax];

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];
}

vector <pli> adj[nmax];

void build_virtual(vector <int> &nodes) {

    int m = ssize(nodes);
    sort(all(nodes), [&] (int x, int y) {
        return lca.ein[x] < lca.ein[y];
    }) ; 
    rep (i, 0, m - 2) {
        int u = nodes[i];
        int v = nodes[i + 1];
        int anc = lca.get_lca(u, v);
        nodes.push_back(anc);
    }

    sort(all(nodes), [&] (int x, int y) {
        return lca.ein[x] < lca.ein[y];
    }) ; 
    nodes.resize(unique(all(nodes)) - nodes.begin());
    m = ssize(nodes);

    rep (i, 0, m - 1) {
        adj[nodes[i]].clear();
    }

    rep (i, 0, m - 2) {
        int u = lca.get_lca(nodes[i], nodes[i + 1]);
        int v = nodes[i + 1];
        ll w = get_dist(u, v);
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});
    }
} 

int n, Q, a[nmax], b[nmax], wei[nmax];

void Init(int n, int a[], int b[], int wei[]) {
    rep (i, 0, n - 2) {
        int u = a[i];
        int v = b[i];
        int w = wei[i];
        ++u; ++v;
        // debug(u, v, w);
        G[u].push_back({w, v});
        G[v].push_back({w, u});
    }   

    lca.build_lca();
    dfs(1, 0);

}

ll dist[nmax];

int S, T, X[nmax], Y[nmax];

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

    vector <int> nodes;

    rep (i, 0, S - 1) {
        X[i]++;
        nodes.push_back(X[i]);
        // debug(X[i]);
    }
    rep (i, 0, T - 1) {
        Y[i]++;
        nodes.push_back(Y[i]);
        // debug(Y[i]);
    }

    build_virtual(nodes);

    // repv (v, nodes) {
    //     cerr <<v  << sp;
    // }
    // EL

    repv (v, nodes) dist[v] = LINF;

    priority_queue <pli, vector <pli>, greater <pli>> pq;
    rep (i, 0, S - 1) {
        dist[X[i]] = 0;
        pq.push({dist[X[i]], X[i]});
    }

    while (pq.empty() == 0) {
        auto cur_v = pq.top();
        pq.pop();
        int u = cur_v.se;
        ll du = cur_v.fi;
        if (dist[u] != du) continue;
        repv (e, adj[u]) {
            int v = e.se;
            ll w = e.fi;
            if (minimize(dist[v], dist[u] + w)) {
                pq.push({dist[v], v});
            }
        }
    }

    ll ans = LINF;

    rep (i, 0, T - 1) {
        minimize(ans, dist[Y[i]]);
    }

    return ans;
}

// void tintingyn() {

//     cin >> n >> Q;

//     rep (i, 0, n - 2) {
//         cin >> a[i] >> b[i] >> wei[i];
//         // print(a[i] + 1, b[i] + 1, wei[i]);
//     }

//     Init(n, a, b, wei);

//     rep (_i, 0, Q - 1) {
//         int S, T;
//         cin >> S >> T;
//         // debug(S, T);
//         rep (i, 0, S - 1) cin >> X[i];
//         rep (i, 0, T - 1) cin >> Y[i];

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

//         cout << Query(S, X, T, Y) << nl;
//     }   

// }

// signed main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);

//     //________________________________________________________________

//     #define TASK "3"
//     if(fopen(TASK".inp", "r")) {
//         freopen(TASK".inp", "r", stdin);
//         freopen(TASK".out", "w", stdout);
//     }

//     //________________________________________________________________
    
//     //  CODE FROM HERE ...! 





//     int num_test = 1; 
//     // cin >> num_test;

//     while(num_test--) {

//         tintingyn();

//     }


//     cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" << nl;

//     return 0;
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 51016 KB Output is correct
2 Correct 749 ms 60148 KB Output is correct
3 Correct 731 ms 57928 KB Output is correct
4 Correct 773 ms 67756 KB Output is correct
5 Correct 699 ms 70216 KB Output is correct
6 Correct 533 ms 69448 KB Output is correct
7 Correct 778 ms 69544 KB Output is correct
8 Correct 768 ms 70784 KB Output is correct
9 Correct 694 ms 70204 KB Output is correct
10 Correct 571 ms 67488 KB Output is correct
11 Correct 759 ms 67524 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51280 KB Output is correct
2 Correct 1020 ms 195856 KB Output is correct
3 Correct 1094 ms 214088 KB Output is correct
4 Correct 783 ms 213672 KB Output is correct
5 Correct 978 ms 231244 KB Output is correct
6 Correct 1120 ms 216392 KB Output is correct
7 Correct 971 ms 100424 KB Output is correct
8 Correct 585 ms 100528 KB Output is correct
9 Correct 639 ms 103316 KB Output is correct
10 Correct 909 ms 103244 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 51016 KB Output is correct
2 Correct 749 ms 60148 KB Output is correct
3 Correct 731 ms 57928 KB Output is correct
4 Correct 773 ms 67756 KB Output is correct
5 Correct 699 ms 70216 KB Output is correct
6 Correct 533 ms 69448 KB Output is correct
7 Correct 778 ms 69544 KB Output is correct
8 Correct 768 ms 70784 KB Output is correct
9 Correct 694 ms 70204 KB Output is correct
10 Correct 571 ms 67488 KB Output is correct
11 Correct 759 ms 67524 KB Output is correct
12 Correct 24 ms 51280 KB Output is correct
13 Correct 1020 ms 195856 KB Output is correct
14 Correct 1094 ms 214088 KB Output is correct
15 Correct 783 ms 213672 KB Output is correct
16 Correct 978 ms 231244 KB Output is correct
17 Correct 1120 ms 216392 KB Output is correct
18 Correct 971 ms 100424 KB Output is correct
19 Correct 585 ms 100528 KB Output is correct
20 Correct 639 ms 103316 KB Output is correct
21 Correct 909 ms 103244 KB Output is correct
22 Correct 2729 ms 232472 KB Output is correct
23 Correct 2054 ms 231424 KB Output is correct
24 Correct 2532 ms 234664 KB Output is correct
25 Correct 2411 ms 235616 KB Output is correct
26 Correct 2103 ms 229448 KB Output is correct
27 Correct 2221 ms 240540 KB Output is correct
28 Correct 1484 ms 229400 KB Output is correct
29 Correct 1997 ms 225656 KB Output is correct
30 Correct 1925 ms 226500 KB Output is correct
31 Correct 1906 ms 227228 KB Output is correct
32 Correct 1117 ms 105544 KB Output is correct
33 Correct 869 ms 104264 KB Output is correct
34 Correct 1302 ms 100256 KB Output is correct
35 Correct 1216 ms 101168 KB Output is correct
36 Correct 1198 ms 100380 KB Output is correct
37 Correct 1268 ms 100168 KB Output is correct