oj.uz

답안 #935271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935271 2024-02-29T02:30:20 Z VinhLuu 공장들 (JOI14_factories) C++17
0 / 100
 5544 ms 131128 KB 
// REPUTATION RATING = -100

#include "factories.h"

#include <bits/stdc++.h>
//#define int 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<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 5e5 + 5;
const ll oo = 1e16;
const int mod = 1e9 + 7;

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

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

vector<pii> p[N];

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

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

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

void update(int i,int 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];
    }
}

int get(int l,int r){
    r++;
    int 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(int i = 0; i < n - 1; i ++){
        int 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(int i = 1; i <= 2 * n; i ++) st[i] = 0;
}

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

//    ll kq = (ll)1e18;
//    for(int i = 0; i < S; i ++)
//        for(int 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(), [] (int x,int y){return in[x] <= in[y];});
    vector<int> R;

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

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

        p[s.top()].pb({R[i], w});
        p[R[i]].pb({s.top(), w});
        s.push(R[i]);
    }
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    for(int i = 0; i < S; i ++) pq.push({dp[X[i]] = 0, X[i]});
    while(!pq.empty()){
        int w = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if(w > dp[u]) continue;
        for(auto jj : p[u]){
            int j = jj.fi;
            int ts = jj.se;
            if(dp[j] > dp[u] + ts) pq.push({dp[j] = dp[u] + ts, j});
        }
    }
    for(int i = 0; i < T; i ++) ans = min(ans, dp[Y[i]]);
    return ans;
}

//#define LOCAL

int 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(int i = 0; i < n - 1; i ++){
        cin >> A[i] >> B[i] >> C[i];
    }
    Init(n, A, B, C);
    while(q--){
        cin >> S >> T;

        for(int i = 0; i < S; i ++) cin >> X[i];
        for(int 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:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i = 1; i < vr.size(); i ++){
      |                    ~~^~~~~~~~~~~
factories.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i = 1; i < R.size(); i ++){
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 43356 KB Output is correct
2 Correct 1155 ms 48008 KB Output is correct
3 Correct 1113 ms 57708 KB Output is correct
4 Incorrect 1102 ms 57588 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 43352 KB Output is correct
2 Correct 5122 ms 127972 KB Output is correct
3 Incorrect 5544 ms 131128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 43356 KB Output is correct
2 Correct 1155 ms 48008 KB Output is correct
3 Correct 1113 ms 57708 KB Output is correct
4 Incorrect 1102 ms 57588 KB Output isn't correct
5 Halted 0 ms 0 KB -