oj.uz

Submission #935283

# Submission time Handle Problem Language Result Execution time Memory
935283 2024-02-29T03:01:05 Z VinhLuu Factories (JOI14_factories) C++17
100 / 100
 4151 ms 220612 KB 
// 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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 43356 KB Output is correct
2 Correct 1159 ms 50280 KB Output is correct
3 Correct 1217 ms 50152 KB Output is correct
4 Correct 1094 ms 50304 KB Output is correct
5 Correct 1049 ms 59976 KB Output is correct
6 Correct 944 ms 59728 KB Output is correct
7 Correct 1205 ms 59728 KB Output is correct
8 Correct 1145 ms 59800 KB Output is correct
9 Correct 1073 ms 60008 KB Output is correct
10 Correct 889 ms 59480 KB Output is correct
11 Correct 1216 ms 59480 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43768 KB Output is correct
2 Correct 1285 ms 175544 KB Output is correct
3 Correct 1902 ms 178768 KB Output is correct
4 Correct 931 ms 173488 KB Output is correct
5 Correct 2586 ms 196540 KB Output is correct
6 Correct 2054 ms 179024 KB Output is correct
7 Correct 1774 ms 81236 KB Output is correct
8 Correct 1018 ms 80320 KB Output is correct
9 Correct 2300 ms 83576 KB Output is correct
10 Correct 1907 ms 81664 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 43356 KB Output is correct
2 Correct 1159 ms 50280 KB Output is correct
3 Correct 1217 ms 50152 KB Output is correct
4 Correct 1094 ms 50304 KB Output is correct
5 Correct 1049 ms 59976 KB Output is correct
6 Correct 944 ms 59728 KB Output is correct
7 Correct 1205 ms 59728 KB Output is correct
8 Correct 1145 ms 59800 KB Output is correct
9 Correct 1073 ms 60008 KB Output is correct
10 Correct 889 ms 59480 KB Output is correct
11 Correct 1216 ms 59480 KB Output is correct
12 Correct 9 ms 43768 KB Output is correct
13 Correct 1285 ms 175544 KB Output is correct
14 Correct 1902 ms 178768 KB Output is correct
15 Correct 931 ms 173488 KB Output is correct
16 Correct 2586 ms 196540 KB Output is correct
17 Correct 2054 ms 179024 KB Output is correct
18 Correct 1774 ms 81236 KB Output is correct
19 Correct 1018 ms 80320 KB Output is correct
20 Correct 2300 ms 83576 KB Output is correct
21 Correct 1907 ms 81664 KB Output is correct
22 Correct 3427 ms 202920 KB Output is correct
23 Correct 2693 ms 204752 KB Output is correct
24 Correct 4151 ms 206744 KB Output is correct
25 Correct 4013 ms 207680 KB Output is correct
26 Correct 3669 ms 202184 KB Output is correct
27 Correct 3449 ms 220612 KB Output is correct
28 Correct 2068 ms 202472 KB Output is correct
29 Correct 3585 ms 201844 KB Output is correct
30 Correct 3673 ms 201544 KB Output is correct
31 Correct 3493 ms 201904 KB Output is correct
32 Correct 1889 ms 101884 KB Output is correct
33 Correct 1409 ms 97888 KB Output is correct
34 Correct 1736 ms 93860 KB Output is correct
35 Correct 1909 ms 93648 KB Output is correct
36 Correct 2278 ms 94524 KB Output is correct
37 Correct 2112 ms 94480 KB Output is correct