Submission #935283

#	Time	Username	Problem	Language	Result	Execution time	Memory
935283		VinhLuu	Factories (JOI14_factories)	C++17	100 / 100	4151 ms	220612 KiB

factories

// REPUTATION RATING = -100

#include "factories.h"

#include <bits/stdc++.h>
//#define ll long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<ll,ll> pii;
typedef tuple<ll,ll,ll> tp;
const ll N = 5e5 + 5;
const ll oo = 1e16;
const ll mod = 1e9 + 7;

ll n, q, f[N][22], in[N], en[N], demin, a[N];

ll d[N], dp[N];
ll st[N << 1];

vector<pii> p[N];

void dfs(ll u,ll v){
    in[u] = ++demin;
    a[in[u]] = u;
//    cout << u << " ";
    if(u == 1) for(ll i = 0; i <= 20; i ++) f[u][i] = u;
    else{
        f[u][0] = v;
        for(ll i = 1; i <= 20; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for(auto jj : p[u]){
        ll j = jj.fi;
        ll w = jj.se;
        if(j == v) continue;
        d[j] = d[u] + w;
        dfs(j, u);
    }
    en[u] = demin;
}

bool kt(ll u,ll v){
    return in[u] <= in[v] && in[v] <= en[u];
}

ll lca(ll u,ll v){
    if(kt(u, v)) return u;
    else{
        ll kq = u;
        for(ll i = 20; i >= 0; i --){
            if(kt(f[u][i], v)) kq = f[u][i];
            else u = f[u][i];
        }
        return kq;
    }
}

void update(ll i,ll x){
    i += n - 1;
    st[i] = x;
    while(i > 1){
        i /= 2;
        if(d[st[i << 1]] < d[st[i << 1|1]]) st[i] = st[i << 1];
        else st[i] = st[i << 1|1];
    }
}

ll get(ll l,ll r){
    r++;
    ll ret = 0;
    for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
        if(l & 1){
            if(d[st[l]] < d[ret]) ret = st[l];
            l++;
        }
        if(r & 1){
            --r;
            if(d[st[r]] < d[ret]) ret = st[r];
        }
    }
    return ret;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    d[0] = oo;
    for(ll i = 0; i < n - 1; i ++){
        ll x = A[i] + 1, y = B[i] + 1, w = D[i];
//        cerr << x << " " << y << " " << w << "\n";
        p[x].pb({y, w});
        p[y].pb({x, w});
    }
    dfs(1, 0);
//    cout << "\n";
    for(ll i = 1; i <= 2 * n; i ++) st[i] = 0;
}

long long Query(int S, int X[], int T, int Y[]){
    vector<ll> vr;
    for(ll i = 0; i < S; i ++) vr.pb(++X[i]);
    for(ll i = 0; i < T; i ++) vr.pb(++Y[i]);
    ll ans = (ll)1e18;

//    ll kq = (ll)1e18;
//    for(ll i = 0; i < S; i ++)
//        for(ll j = 0; j < T; j ++)
//            kq = min(kq, d[X[i]] + d[Y[j]] - 1LL * 2 * d[lca(X[i], Y[j])]);
//    return kq;

//    cerr << S << " " << T << "\n";

    sort(vr.begin(), vr.end(), [] (ll x,ll y){return in[x] <= in[y];});
    vector<ll> R;

//    for(auto j : vr) cerr << j << " ";
//    cerr << "\n";

    R.pb(vr[0]);
    p[vr[0]].clear();
    for(ll i = 1; i < vr.size(); i ++){
        ll u = lca(vr[i], vr[i - 1]);
        R.pb(vr[i]);
        R.pb(u);
//        cerr << vr[i] << " " << vr[i - 1] << " " << u << "d\n";
        p[vr[i]].clear();
        p[u].clear();
    }
    sort(all(R), [] (ll x,ll y){return x < y;});
    R.resize(unique(all(R)) - R.begin());
    sort(all(R), [] (ll x,ll y){return in[x] <= in[y];});
//    for(auto j : R) cerr << j << " ";
//    cerr << "\n";
    stack<ll> s;
    s.push(R[0]);
    dp[R[0]] = oo;
    for(ll i = 1; i < R.size(); i ++){
        dp[R[i]] = oo;
        while(!s.empty()  && !kt(s.top(), R[i])) s.pop();
        ll w = d[R[i]] - d[s.top()];

//        cerr << R[i] << " " << s.top() << " " << w << "g\n";

        p[s.top()].pb({R[i], w});
        p[R[i]].pb({s.top(), w});
//        cerr << p[R[i]].back().se << "gg\n";
        s.push(R[i]);
    }
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    for(ll i = 0; i < S; i ++) pq.push({dp[X[i]] = 0, X[i]});
    while(!pq.empty()){
        ll w = pq.top().fi;
        ll u = pq.top().se;
        pq.pop();
        if(w > dp[u]) continue;
//        cerr << u << " " << w << "f\n";
        for(auto jj : p[u]){
            ll j = jj.fi;
            ll ts = jj.se;

//            cerr << j << " " << ts << "f\n";

            if(dp[j] > dp[u] + ts){
                pq.push({dp[j] = dp[u] + ts, j});
//                cerr << j << " " << dp[j] << " " << dp[u] << " " << ts << "g\n";
            }
        }
    }
//    cerr << "f\n";
    for(ll i = 0; i < T; i ++) ans = min(ans, dp[Y[i]]);
    return ans;
}

//#define LOCAL

ll A[N], B[N], C[N], X[N], Y[N], S, T;

#ifdef LOCAL

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

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n >> q;
    for(ll i = 0; i < n - 1; i ++){
        cin >> A[i] >> B[i] >> C[i];
    }
    Init(n, A, B, C);
    while(q--){
        cin >> S >> T;

        for(ll i = 0; i < S; i ++) cin >> X[i];
        for(ll i = 0; i < T; i ++) cin >> Y[i];

        cout << Query(S, X, T, Y) << "\n";
    }
}
#endif // LOCAL

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:125:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(ll i = 1; i < vr.size(); i ++){
      |                   ~~^~~~~~~~~~~
factories.cpp:141:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(ll i = 1; i < R.size(); i ++){
      |                   ~~^~~~~~~~~~

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