oj.uz

Submission #656578

# Submission time Handle Problem Language Result Execution time Memory
656578 2022-11-08T02:00:38 Z minhcool Factories (JOI14_factories) C++17
18 / 100
 8000 ms 178700 KB 
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const ll N = 5e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7;

ll n;
vector<pair<ll, ll>> Adj[N];

ll d1[N], d2[N];

ll anc[N][20];
//dist[N][20];

void dfs(int u, int p){
    for(auto it : Adj[u]){
        int v = it.fi, w = it.se;
        if(v == p) continue;
        d1[v] = d1[u] + 1;
        d2[v] = d2[u] + w;
        anc[v][0] = u;
        //dist[v][0] = w;
        dfs(v, u);
    }
}

void prep(){
    for(int i = 1; i <= 19; i++){
        for(int j = 1; j <= n; j++){
            anc[j][i] = anc[anc[j][i - 1]][i - 1];
            //dist[j][i] = dist[j][i - 1] + dist[anc[j][i - 1]][i - 1];
        }
    }
}

int lca(int x, int y){
    if(d1[x] > d1[y]) swap(x, y);
    for(int i = 19; i >= 0; i--){
        if((d1[x] + (1LL << i)) <= d1[y]) y = anc[y][i];
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i--){
        if(anc[x][i] != anc[y][i]){
            x = anc[x][i], y = anc[y][i];
        }
    }
    return anc[x][0];
}

ll dist(int x, int y){
    return d2[x] + d2[y] - 2 * d2[lca(x, y)];
}

int cnt;
int pos[N], l[N], r[N];
int arr[N];

void pre_dfs(int u, int p){
    cnt++;
    pos[u] = l[u] = cnt;
    arr[cnt] = u;
    for(auto it : Adj[u]){
        int v = it.fi;
        if(v == p) continue;
        pre_dfs(v, u);
    }
    r[u] = cnt;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i = 0; i < (n - 1); i++){
        Adj[A[i] + 1].pb({B[i] + 1, D[i]});
        Adj[B[i] + 1].pb({A[i] + 1, D[i]});
    }
    pre_dfs(1, 1);
    dfs(1, 1);
    prep();
}

ll IT[N << 2], lazy[N << 2];

bool choose1[N], choose2[N];

void laz(int id){
    if(lazy[id] == 0) return;
    int t = lazy[id];
    IT[id << 1] += t;
    lazy[id << 1] += t;
    IT[id << 1 | 1] += t;
    lazy[id << 1 | 1] += t;
    lazy[id] = 0;
    return;
}

void upd(int id, int l, int r, int L, int R, int val){
    if(l > R || r < L || l > r) return;
    if(l >= L && r <= R){
        IT[id] += val;
        lazy[id] += val;
        return;
    }
    laz(id);
    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, L, R, val);
    upd(id << 1 | 1, mid + 1, r, L, R, val);
    IT[id] = min(IT[id << 1], IT[id << 1 | 1]);
}

ll total = 0, answer = oo;

void main_dfs(int u, int p){
    //cout << u << "\n";
    if(choose2[u]){
        //cout << total << " " << IT[1] << "\n";
        answer = min(answer, total + IT[1]);
    }
    for(auto it : Adj[u]){
        int v = it.fi, w = it.se;
        if(v == p) continue;
        total += w;
        upd(1, 1, n, l[v], r[v], -(2 * w));
        //upd(1, 1, n, l[v], r[v], -w);
        //upd(1, 1, n, 1, l[v] - 1, w);
        //upd(1, 1, n, r[v] + 1, n, w);
        main_dfs(v, u);
        total -= w;
        upd(1, 1, n, l[v], r[v], (2 * w));
    }
}

void ini(int id, int l, int r){
    lazy[id] = 0;
    if(l == r){
        if(choose1[arr[l]]) IT[id] = d2[arr[l]];
        else IT[id] = oo;
        return;
    }
    int mid = (l + r) >> 1;
    ini(id << 1, l, mid);
    ini(id << 1 | 1, mid + 1, r);
    IT[id] = min(IT[id << 1], IT[id << 1 | 1]);
}

ll Query(int S, int X[], int T, int Y[]){
    if(S <= 5000 && T <= 5000){
        ll ans = oo;
        for(int i = 0; i < S; i++){
            for(int j = 0; j < T; j++) ans = min(ans, dist(X[i] + 1, Y[j] + 1));
        }
        return ans;
    }
    else{
        answer = oo;
        //vis.clear();
        for(int i = 0; i < S; i++) choose1[X[i] + 1] = 1;
        for(int i = 0; i < T; i++) choose2[Y[i] + 1] = 1;
        ini(1, 1, n);
        main_dfs(1, 1);
        for(int i = 0; i < S; i++) choose1[X[i] + 1] = 0;
        for(int i = 0; i < T; i++) choose2[Y[i] + 1] = 0;
        return answer;
        //vis.clear();
    }
}

/*
void process(){
    int n, q;
    vector<int> a(n - 1), b(n - 1), d(n - 1);
    cin >> n >> q;
    for(int i = 0; i < (n - 1); i++){
        cin >> a[i] >> b[i] >> d[i];
    }
    Init(n, a, b, d);
    while(q--){
        int sz1, sz2;
        vector<int> vc1, vc2;
        cin >> sz1 >> sz2;
        vc1.resize(sz1);
        for(int i = 0; i < sz1; i++) cin >> vc1[i];
        vc2.resize(sz2);
        for(int i = 0; i < sz2; i++) cin >> vc2[i];
        cout << Query(sz1, vc1, sz2, vc2) << "\n"; 
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    process();
}*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 12500 KB Output is correct
2 Execution timed out 8047 ms 21312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 1656 ms 144428 KB Output is correct
3 Correct 4001 ms 148220 KB Output is correct
4 Correct 1056 ms 142120 KB Output is correct
5 Correct 3279 ms 178700 KB Output is correct
6 Correct 3046 ms 149544 KB Output is correct
7 Correct 5450 ms 47312 KB Output is correct
8 Correct 1279 ms 47032 KB Output is correct
9 Correct 5480 ms 51928 KB Output is correct
10 Correct 4493 ms 48616 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 12500 KB Output is correct
2 Execution timed out 8047 ms 21312 KB Time limit exceeded
3 Halted 0 ms 0 KB -