Submission #1180971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180971		Alish	Factories (JOI14_factories)	C++20	100 / 100	2107 ms	160612 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double     ld;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("input19.txt" , "r" , stdin) ;


const int N = 5e5+23, L=19;
const ll INF=1e18+23;

vector<pii> g[N];
int dead[N];
int sz[N], H[N], par[N];
ll h[N][L];
ll dp[N];
int n;

void dfs(int v, int p=0){
    sz[v]=1;
    for (auto [u, w]: g[v]) if(u!=p && !dead[u]){
        dfs(u, v);
        sz[v]+=sz[u];
    }
}

int cent(int v, int num, int p=0){
    for(auto [u, w]: g[v]) if(u!=p && !dead[u] && 2*sz[u]>num) return cent(u, num, v);
    return v;
}

void DFS(int v, int hh, int p=0){
    for (auto [u, w]: g[v])if(u!=p && !dead[u]){
        h[u][hh]=h[v][hh]+w;
        DFS(u, hh, v);
    }
}

void Dec(int v=1, int hh=0, int p=0){
    dfs(v);
    v=cent(v, sz[v]);
    H[v]=hh;
    par[v]=p;
    DFS(v, hh);
    dead[v]=1;
    for (auto [u, w]: g[v]) if(!dead[u]) Dec(u, hh+1, v);
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for (int i=0; i<n-1; i++){
        A[i]++;
        B[i]++;
        g[A[i]].pb({B[i], D[i]});
        g[B[i]].pb({A[i], D[i]});
    }
    Dec();
    for (int i=1; i<=n; i++) dp[i]=INF;
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i=0; i<S; i++) X[i]++;
    for (int i=0; i<T; i++) Y[i]++;

    for (int i=0; i<S; i++){
        int v=X[i];
        while(v){
            dp[v]=min(dp[v], h[X[i]][H[v]]);
            v=par[v];
        }
    }

    ll ans=INF;

    for (int i=0; i<T; i++){
        int v=Y[i];
        while(v){
            ans=min(ans, dp[v]+h[Y[i]][H[v]]);
            v=par[v];
        }
    }
    for (int i=0; i<S; i++){
        int v=X[i];
        while(v){
            dp[v]=INF;
            v=par[v];
        }
    }
    return ans;
}

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