Submission #1161003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161003		hainam2k9	Factories (JOI14_factories)	C++20	15 / 100	8089 ms	87856 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 5e5+5;
const string NAME = "";
int n,par[MAXN][20],depth[MAXN];
ll dist[MAXN];
vector<pair<int,int>> adj[MAXN];
void dfsInit(int u){
    for(pair<int,int>& v : adj[u])
        if(v.fi!=par[u][0]){
            dist[v.fi]=dist[u]+v.se, par[v.fi][0]=u, depth[v.fi]=depth[u]+1;
            for(int i = 1; i<20; ++i)
                par[v.fi][i]=par[par[v.fi][i-1]][i-1];
            dfsInit(v.fi);
        }
}
void Init(int N, int a[], int b[], int d[]){
    n=N;
    for(int i = 0; i<n; ++i)
        ++a[i], ++b[i], adj[a[i]].pb(b[i],d[i]), adj[b[i]].pb(a[i],d[i]);
    dfsInit(1);
}
inline void lift(int &x, int k){
    for(int i = 0; i<20; ++i)
        if((k>>i)&1) x=par[x][i];
}
inline int LCA(int x, int y){
    if(depth[x]!=depth[y]){
        if(depth[x]<depth[y]) swap(x,y);
        lift(x,depth[x]-depth[y]);
    }
    if(x==y) return x;
    for(int i = 19; i>=0; --i)
        if(par[x][i]!=par[y][i]) x=par[x][i], y=par[y][i];
    return par[x][0];
}
ll rs;
bool A[MAXN],B[MAXN];
pair<ll,ll> dfs(int u){
    ll minA=1e18, minB=1e18;
    for(pair<int,int>& v : adj[u])
        if(v.fi!=par[u][0]){
            pair<ll,ll> p = dfs(v.fi);
            minA=min(minA,p.fi), minB=min(minB,p.se);
        }
    if(A[u]) minA=min(minA,dist[u]);
    if(B[u]) minB=min(minB,dist[u]);
    rs=min(rs,minA+minB-2*dist[u]);
    return {minA,minB};
}
ll Query(int n, int a[], int m, int b[]){
    rs=1e18;
    for(int i = 0; i<n; ++i)
        ++a[i];
    for(int i = 0; i<m; ++i)
        ++b[i];
    if(1ll*n*m*__lg(n)<=n){
        for(int i = 0; i<n; ++i)
            for(int j = 0; j<m; ++j)
                rs=min(rs,dist[a[i]]+dist[b[j]]-2*dist[LCA(a[i],b[j])]);
        return rs;
    }
    for(int i = 0; i<n; ++i)
        A[a[i]]=1;
    for(int i = 0; i<m; ++i)
        B[b[i]]=1;
    dfs(1);
    for(int i = 0; i<n; ++i)
        A[a[i]]=0;
    for(int i = 0; i<m; ++i)
        B[b[i]]=0;
    return rs;
}

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