Submission #1231426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231426		lmduc270410	Factories (JOI14_factories)	C++20	100 / 100	1696 ms	151464 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
#define lll __int128_t
#define f first
#define s second
using namespace std;
const int mod = 1e9 + 7;
const int N = 5e5 + 5, M = 1e6 + 5;
const int base = 311;
const ll INF = LLONG_MAX;
const int inf = INT_MAX;

int n, q, depth[N], tin[N], tout[N], dfs_timer, par[N][20];
ll dis[N];
vector<pair<int, int>> g[N];

void dfs(int u, int e){
    tin[u] = ++dfs_timer;
    for(auto [v, w] : g[u]) if(v != e){
        depth[v] = depth[u] + 1; par[v][0] = u; dis[v] = dis[u] + w;
        for(int i = 1; i <= 18; ++i){
            par[v][i] = par[par[v][i-1]][i-1];
        }
        dfs(v, u);
    }
    tout[u] = dfs_timer;
}

bool dfsTimer(int u, int v){
    return tin[u] < tin[v];
}

bool inside(int u, int v){
    return tin[u] <= tin[v] and tout[v] <= tout[u];
}

int getLCA(int u, int v){
    if(inside(u, v)) return u;
    if(inside(v, u)) return v;
    for(int i = 18; i >= 0; --i){
        if(depth[u] >= (1<<i) and !inside(par[u][i], v)){
            u = par[u][i];
        }
    }
    return par[u][0];
}

int k, ns, nt, a[N];
vector<pair<int, ll>> minigraph[N];
stack<int> st;

short ds[N], d[N];

ll dp[3][N];

void solve(int u, int e){
	dp[1][u] = dp[2][u] = INF;
	if(ds[u]) dp[ds[u]][u] = 0;
	for(auto [v, w] : minigraph[u]){
		solve(v, u);
		if(dp[1][v] != INF) dp[1][u] = min(dp[1][u], dp[1][v] + w);
		if(dp[2][v] != INF) dp[2][u] = min(dp[2][u], dp[2][v] + w);
	}
}

long long Query(int S, int X[], int T, int Y[]){
	ns = S; nt = T;
    for(int i = 1; i <= ns; ++i){
        a[i] = X[i - 1];
        ds[a[i]] = 1;
    }
    for(int i = ns + 1; i <= ns + nt; i++){
    	a[i] = Y[i - ns - 1];
    	ds[a[i]] = 2;
	}
	k = ns + nt;
    sort(a + 1, a + 1 + k, dfsTimer);
    
    for(int i = 1; i < k; ++i){
        a[i+k] = getLCA(a[i], a[i+1]);
    }
    k = 2 * k - 1;
    sort(a + 1, a + 1 + k, dfsTimer); 
    k = unique(a + 1, a + 1 + k) - a - 1;

    while(!st.empty()) st.pop();
    st.push(a[1]);
    
    for(int i = 2; i <= k; ++i){
        while(!inside(st.top(), a[i])){
            st.pop();
        }
        minigraph[st.top()].push_back({a[i], dis[a[i]] - dis[st.top()]});
        st.push(a[i]);
    }
    
    solve(a[1], -1); ll ans = INF;
    for(int i = 1; i <= k; i++){
    	int u = a[i];
    	if(dp[1][u] != INF && dp[2][u] != INF) ans = min(ans, dp[1][u] + dp[2][u]);
	}
	for(int i = 1; i <= k; i++){
		minigraph[a[i]].clear();
		ds[a[i]] = 0;
	}
	return ans;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i=1; i<n; ++i){
        int u = A[i - 1], v = B[i - 1], w = D[i - 1];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    for(int i = 1; i <= n; i++){
    	ds[i] = 0;
	}
	
    dfs(0, 0);
}

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