Submission #1292124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292124		torment	Factories (JOI14_factories)	C++20	33 / 100	8098 ms	255884 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
const int B = 1500;
vector<array<int, 2>>G[N];
int tin[N], TIME = 0;
long long d[N], dp[2][N];
vector<long long>dEuler = {-1};
struct SparseTable{
    vector<vector<long long>>sTable;
    vector<int>LOG;
    void init(){
        int n = dEuler.size();
        LOG.resize(n + 1);
        LOG[1] = 0;
        for(int i = 2;i <= n;++i){
            LOG[i] = LOG[i >> 1] + 1;
        }
        sTable.resize(LOG[n] + 1);
        for(int i = 0;i <= LOG[n];++i){
            sTable[i].resize(n + 1);
        }
        for(int i = 1;i <= n;++i){
            sTable[0][i] = dEuler[i];
        }
        for(int i = 1;i <= LOG[n];++i){
            for(int j = 1;j + (1 << i) - 1 <= n;++j){
                sTable[i][j] = min(sTable[i - 1][j], sTable[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    long long Query(int l, int r){
        if(l > r)swap(l, r);
        int lg = LOG[r - l + 1];
        return min(sTable[lg][l], sTable[lg][r - (1 << lg) + 1]);
    }
}table;
void dfs(int node, int par){
    tin[node] = ++TIME;
    dEuler.push_back(d[node]);
    for(auto &[v, w] : G[node]){
        if(v == par)continue;
        d[v] = d[node] + w;
        dfs(v, node);
        dEuler.push_back(d[node]);
        TIME++;
    }
}
void Bdfs(int node, int par, long long &mn){
    long long mnd[2];
    mnd[0] = mnd[1] = 1e18;
    for(auto &[v, w] : G[node]){
        if(v == par)continue;
        Bdfs(v, node, mn);
        dp[0][node] = min(dp[0][node], dp[0][v]);
        dp[1][node] = min(dp[1][node], dp[1][v]);
    }
    mnd[0] = dp[0][node];
    mnd[1] = dp[1][node];
    for(auto &[v, w] : G[node]){
        if(v == par)continue;
        mn = min(mn, mnd[0] + dp[1][v] - 2 * d[node]);
        mn = min(mn, mnd[1] + dp[0][v] - 2 * d[node]);
    }
}
void Init(int N, int A[], int B[], int D[]){
    for(int i = 0;i < N - 1;++i){
        G[A[i]].push_back({B[i], D[i]});
        G[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0);
    table.init();
}
long long Query(int S, int X[], int T, int Y[]){
    long long mn = 1e18;
    if(S >= B){
        for(int i = 0;i < N;++i){
            dp[0][i] = dp[1][i] = 1e18;
        }
        for(int i = 0;i < S;++i){
            dp[0][X[i]] = d[X[i]];
        }
        for(int i = 0;i < T;++i){
            dp[1][Y[i]] = d[Y[i]];
        }
        Bdfs(0, 0, mn);
    }
    else{
        for(int i = 0;i < S;++i){
            for(int j = 0;j < T;++j){
                mn = min(mn, d[X[i]] + d[Y[j]] - 2 * table.Query(tin[X[i]], tin[Y[j]]));
            }
        }
    }
    return mn;
}   
// int main(){
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     int n, q;
//     cin >> n >> q;
//     int a[n - 1], b[n - 1], d[n - 1];
//     for(int i = 0;i < n - 1;++i){
//         cin >> a[i] >> b[i] >> d[i];
//     }
//     Init(n, a, b, d);
//     while(q--){
//         int s, t;
//         cin >> s >> t;
//         int x[s], y[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';
//     }
// }

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