제출 #1190363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190363		boclobanchat	Factories (JOI14_factories)	C++20	100 / 100	1674 ms	299344 KiB

factories

#include"factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define il pair<int,long long>
#define fi first
#define se second
const int MAXN=1e6+5;
const long long INF=1e18;
int dt[MAXN],L[MAXN],R[MAXN],tag[MAXN],tdfs=0,nn;
long long dis[MAXN],dp[MAXN][2],ans;
vector<ii> ds[MAXN];
vector<il> sd[MAXN];
ii sp[MAXN][21];
bool ck[MAXN];
bool comp(int a,int b) { return L[a]<L[b]; }
int getlog(long long n) { return 63-__builtin_clzll(n); }
void minimize(long long& a,long long b)
{
	if(a>b) a=b;
}
void dfs(int i,int pre)
{
	L[i]=R[i]=++tdfs,sp[tdfs][0]={dt[i],i};
	for(auto v:ds[i]) if(v.fi!=pre)
	{
		dis[v.fi]=dis[i]+v.se,dt[v.fi]=dt[i]+1;
		dfs(v.fi,i);
		R[i]=++tdfs,sp[tdfs][0]={dt[i],i};
	}
}
int lca(int a,int b)
{
	int l=min(L[a],L[b]),r=max(R[a],R[b]),lg=getlog(r-l+1);
	return min(sp[l][lg],sp[r-(1<<lg)+1][lg]).se;
}
void dfsus(int i,int pre)
{
	for(auto v:sd[i]) if(v.fi!=pre)
	{
		dfsus(v.fi,i);
		minimize(dp[i][0],dp[v.fi][0]+v.se);
		minimize(dp[i][1],dp[v.fi][1]+v.se);
	}
	minimize(ans,dp[i][0]+dp[i][1]);
}
void Init(int n,int A[],int B[],int D[])
{
	nn=n;
	for(int i=0;i<n-1;i++) ds[A[i]].push_back({B[i],D[i]}),ds[B[i]].push_back({A[i],D[i]});
	dfs(0,0);
	for(int j=1;(1<<j)<=tdfs;j++) for(int i=1;i<=tdfs-(1<<j)+1;i++) sp[i][j]=min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
long long Query(int s,int X[],int t,int Y[])
{
	ans=INF;
	vector<int> vi;
	for(int i=0;i<s;i++) vi.push_back(X[i]);
	for(int i=0;i<t;i++) vi.push_back(Y[i]);
	sort(vi.begin(),vi.end(),comp);
	int sz=vi.size();
	for(int i=0;i<sz-1;i++) vi.push_back(lca(vi[i],vi[i+1]));
	sort(vi.begin(),vi.end(),comp);
	vi.erase(unique(vi.begin(),vi.end()),vi.end());
	stack<int> st;
	for(auto v:vi)
	{
		while(!st.empty()&&!(L[st.top()]<=L[v]&&R[v]<=R[st.top()])) st.pop();
		if(!st.empty()) sd[st.top()].push_back({v,dis[v]-dis[st.top()]});
		dp[v][0]=dp[v][1]=INF,st.push(v);
	}
	for(int i=0;i<s;i++) dp[X[i]][0]=0;
	for(int i=0;i<t;i++) dp[Y[i]][1]=0;
	dfsus(vi[0],vi[0]);
	for(auto v:vi) sd[v].clear();
	return ans;
}

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