oj.uz

Submission #552481

# Submission time Handle Problem Language Result Execution time Memory
552481 2022-04-23T08:18:33 Z Jarif_Rahman Factories (JOI14_factories) C++17
100 / 100
 3304 ms 217972 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct HLD{
    int n;
    vector<pair<ll, int>> *v;
    int *depth, *sz, *p, *top, *id;
    ll *sm;
    int cnt = 0;

    HLD(int _n){
        n = _n;
        v = new vector<pair<ll, int>>[n];
    }

    void pre_dfs(int nd, int ss, int d){
        for(auto [x, w]: v[nd]) if(x != ss) pre_dfs(x, nd, d+1);
        for(auto [x, w]: v[nd]) if(x != ss) sz[nd]+=sz[x];
        depth[nd] = d;
        p[nd] = ss;
    }

    void dfs(int nd, int ss, ll W, int tp){
        top[nd] = tp;
        id[nd] = cnt;
        sm[id[nd]] = W;
        cnt++;

        int mx = 0, in = -1, inw = -1;
        for(auto [x, w]: v[nd]) if(x != ss && sz[x] > mx) mx = sz[x], in = x, inw = w;

        if(in != -1) dfs(in, nd, inw, tp);
        for(auto [x, w]: v[nd]) if(x != ss && x != in) dfs(x, nd, w, x);
    }

    void init(){
        depth = new int[n];
        p = new int[n];
        sz = new int[n];
        fill(sz, sz+n, 1);
        pre_dfs(0, -1, 0);

        top = new int[n];
        id = new int[n];
        sm = new ll[n];
        fill(sm, sm+n, 0);
        dfs(0, -1, 0, 0);

        for(int i = 1; i < n; i++) sm[i]+=sm[i-1];
    }

    ll sum(int l, int r){
        if(l > r) return 0;
        return sm[r]-(l==0?0:sm[l-1]);
    }

    ll query(int S, int X[], int T, int Y[]){
        ll ans = 1e18;
        priority_queue<tuple<int, int, int, int, ll>> pq;
        for(int i = 0; i < S; i++) pq.push({depth[top[X[i]]], top[X[i]], X[i], 0, 0});
        for(int i = 0; i < T; i++) pq.push({depth[top[Y[i]]], top[Y[i]], Y[i], 1, 0});

        while(!pq.empty()){
            int tp = get<1>(pq.top());
            vector<tuple<int, int, ll>> cur;
            while(!pq.empty() && get<1>(pq.top()) == tp){
                cur.pb({get<2>(pq.top()), get<3>(pq.top()), get<4>(pq.top())});
                pq.pop();
            }
            sort(cur.begin(), cur.end(), [&](tuple<int, int, ll> a, tuple<int, int, ll> b){
                return depth[get<0>(a)] < depth[get<0>(b)];
            });

            int tn[2] = {-1,-1};
            ll tc[2] = {ll(1e18), ll(1e18)};

            for(int i = int(cur.size())-1; i >= 0; i--){
                auto [nd, t, c] = cur[i];
                if(tn[t] == -1 || c < tc[t]+sum(id[nd]+1, id[tn[t]]))
                    tn[t] = nd, tc[t] = c;
                if(tn[1-t] != -1)
                    ans = min(ans, c+tc[1-t]+sum(id[nd]+1, id[tn[1-t]]));
            }

            tc[0] = 1e18, tc[1] = 1e18;

            for(auto [nd, t, c]: cur){
                tc[t] = min(tc[t], sum(id[tp], id[nd])+c);
            }

            if(!pq.empty()){
                for(int i = 0; i < 2; i++)
                    if(tn[i] != -1)
                        pq.push({depth[top[p[tp]]], top[p[tp]], p[tp], i, tc[i]});
            }
        }

        return ans;
    }

};

HLD hld(0);

void Init(int N, int A[], int B[], int D[]){
    hld = HLD(N);
    for(int i = 0; i < N-1; i++){
        hld.v[A[i]].pb({B[i], D[i]});
        hld.v[B[i]].pb({A[i], D[i]});
    }
    hld.init();
}

ll Query(int S, int X[], int T, int Y[]){
    return hld.query(S, X, T, Y);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 724 KB Output is correct
2 Correct 1036 ms 12076 KB Output is correct
3 Correct 921 ms 12220 KB Output is correct
4 Correct 851 ms 12224 KB Output is correct
5 Correct 555 ms 13644 KB Output is correct
6 Correct 839 ms 12108 KB Output is correct
7 Correct 930 ms 12012 KB Output is correct
8 Correct 856 ms 12352 KB Output is correct
9 Correct 550 ms 13416 KB Output is correct
10 Correct 836 ms 12156 KB Output is correct
11 Correct 952 ms 11984 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 2276 ms 64308 KB Output is correct
3 Correct 1375 ms 99656 KB Output is correct
4 Correct 1000 ms 80148 KB Output is correct
5 Correct 1080 ms 217972 KB Output is correct
6 Correct 1402 ms 100176 KB Output is correct
7 Correct 1071 ms 38312 KB Output is correct
8 Correct 846 ms 35508 KB Output is correct
9 Correct 691 ms 52692 KB Output is correct
10 Correct 1244 ms 39416 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 724 KB Output is correct
2 Correct 1036 ms 12076 KB Output is correct
3 Correct 921 ms 12220 KB Output is correct
4 Correct 851 ms 12224 KB Output is correct
5 Correct 555 ms 13644 KB Output is correct
6 Correct 839 ms 12108 KB Output is correct
7 Correct 930 ms 12012 KB Output is correct
8 Correct 856 ms 12352 KB Output is correct
9 Correct 550 ms 13416 KB Output is correct
10 Correct 836 ms 12156 KB Output is correct
11 Correct 952 ms 11984 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 2276 ms 64308 KB Output is correct
14 Correct 1375 ms 99656 KB Output is correct
15 Correct 1000 ms 80148 KB Output is correct
16 Correct 1080 ms 217972 KB Output is correct
17 Correct 1402 ms 100176 KB Output is correct
18 Correct 1071 ms 38312 KB Output is correct
19 Correct 846 ms 35508 KB Output is correct
20 Correct 691 ms 52692 KB Output is correct
21 Correct 1244 ms 39416 KB Output is correct
22 Correct 3018 ms 94856 KB Output is correct
23 Correct 3304 ms 96024 KB Output is correct
24 Correct 2385 ms 109136 KB Output is correct
25 Correct 2333 ms 113308 KB Output is correct
26 Correct 2291 ms 106112 KB Output is correct
27 Correct 1649 ms 201368 KB Output is correct
28 Correct 1715 ms 95604 KB Output is correct
29 Correct 2227 ms 104256 KB Output is correct
30 Correct 2215 ms 101516 KB Output is correct
31 Correct 2211 ms 104316 KB Output is correct
32 Correct 870 ms 58528 KB Output is correct
33 Correct 1216 ms 40580 KB Output is correct
34 Correct 1708 ms 33440 KB Output is correct
35 Correct 1737 ms 33268 KB Output is correct
36 Correct 1269 ms 36468 KB Output is correct
37 Correct 1232 ms 36328 KB Output is correct