Submission #1293062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293062		torment	Factories (JOI14_factories)	C++20	100 / 100	2479 ms	331524 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
vector<array<int, 2>>G[N];
vector<array<long long, 2>>C[N];
bool del[N];
int tsz[N];
long long f[N];
void findsz(int node, int par){
    tsz[node] = 1;
    for(auto &[v, w] : G[node]){
        if(v == par || del[v])continue;
        findsz(v, node);
        tsz[node] += tsz[v];
    }
}
int findcent(int node, int par, int T){
    int mx = -1;
    for(auto &[v, w] : G[node]){
        if(v == par || del[v])continue;
        if(mx == -1 || tsz[mx] < tsz[v]){
            mx = v;
        }
    }
    if(mx == -1 || tsz[mx] <= T / 2)return node;
    return findcent(mx, node, T);
}
void populC(int node, int par, int cent, long long d){
    C[node].push_back({cent, d});
    for(auto &[v, w] : G[node]){
        if(v == par || del[v])continue;
        populC(v, node, cent, d + w);
    }
}
void decompose(int node){
    findsz(node, node);
    int cent = findcent(node, node, tsz[node]);
    populC(cent, cent, cent, 0);
    del[cent] = 1;
    for(auto &[v, w] : G[cent]){
        if(del[v])continue;
        decompose(v);
    }
}   
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]});
    }
    decompose(0);
    for(int i = 0;i < N;++i){
        f[i] = 1e18;
    }
}
long long Query(int S, int X[], int T, int Y[]){
    for(int i = 0;i < S;++i){
        for(auto &[node, dist] : C[X[i]]){
            f[node] = min(f[node], dist);
        }
    }
    long long mn = 1e18;
    for(int i = 0;i < T;++i){
        for(auto &[node, dist] : C[Y[i]]){
            mn = min(mn, dist + f[node]);
        }
    }
    for(int i = 0;i < S;++i){
        for(auto &[node, dist] : C[X[i]]){
            f[node] = 1e18;
        }
    }
    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: 67 / 67