제출 #552469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552469		Jarif_Rahman	공장들 (JOI14_factories)	C++17	15 / 100	8086 ms	116472 KiB

factories

#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<vector<pair<ll, int>>> v;
    vector<int> depth, sz, p, top, id;
    vector<ll> sm;
    int cnt = 0;

    HLD(int _n){
        n = _n;
        v.assign(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.assign(n, 0);
        sz.assign(n, 1);
        p.assign(n, -1);
        pre_dfs(0, -1, 0);

        top.assign(n, -1);
        id.assign(n, -1);
        sm.assign(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(vector<pair<int, int>> sth){
        ll ans = 1e18;
        priority_queue<tuple<int, int, int, int, ll>> pq;
        for(auto [nd, t]: sth) pq.push({depth[top[nd]], top[nd], nd, t, 0});

        while(!pq.empty()){
            int tp = get<1>(pq.top());
            cerr << tp << " -----\n";
            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[]){
    vector<pair<int, int>> sth;
    for(int i = 0; i < S; i++) sth.pb({X[i], 0});
    for(int i = 0; i < T; i++) sth.pb({Y[i], 1});
    return hld.query(sth);
}

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