제출 #1086370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086370		4QT0R	공장들 (JOI14_factories)	C++17	100 / 100	2986 ms	232644 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long

ll oo=1e18;
vector<pair<int,ll>> graph[500003];
ll iter=0;
ll pre[500003];
ll post[500003];
ll dep[500003];
ll real_dep[500003];
ll jmp[500003][20];

int lca(int a, int b){
	if (dep[a]<dep[b])swap(a,b);
	for (int i = 19; i>=0; i--){
		if (dep[jmp[a][i]]>=dep[b])a=jmp[a][i];
	}
	if (a==b)return a;
	for (int i = 19; i>=0; i--){
		if (jmp[a][i]!=jmp[b][i]){
			a=jmp[a][i];
			b=jmp[b][i];
		}
	}
	return jmp[a][0];
}

ll dist(int a, int b){
	if (pre[a]<=pre[b] && post[a]>=post[b])return real_dep[b]-real_dep[a];
	if (pre[a]>=pre[b] && post[a]<=post[b])return real_dep[a]-real_dep[b];
	return real_dep[a]+real_dep[b]-2*real_dep[lca(a,b)];
}

void prep(int v, int p){
	pre[v]=iter++;
	jmp[v][0]=p;
	for (int i = 1; i<20; i++)jmp[v][i]=jmp[jmp[v][i-1]][i-1];
	for (auto [u,d] : graph[v]){
		if (u==p)continue;
		dep[u]=dep[v]+1;
		real_dep[u]=real_dep[v]+d;
		prep(u,v);
	}
	post[v]=iter++;
}

int n;

void Init(int N, int A[], int B[], int D[]){
	n=N;
	for (int i = 0; i<N-1; i++){
		graph[A[i]].push_back({B[i],D[i]});
		graph[B[i]].push_back({A[i],D[i]});
	}
	prep(0,0);
}

ll odl[500003];
ll fin[500003];
ll dp[500003][2];

vector<int> graph2[500003];

ll dfs(int v){
	if (fin[v])dp[v][fin[v]-1]=0;
	ll odp=oo;
	for (auto u : graph2[v]){
		if (v==u)continue;
		odp=min(odp,dfs(u));
		dp[v][0]=min(dp[v][0],dp[u][0]+real_dep[u]-real_dep[v]);
		dp[v][1]=min(dp[v][1],dp[u][1]+real_dep[u]-real_dep[v]);
	}
	graph2[v].clear();
	return min(odp,dp[v][0]+dp[v][1]);
}
ll Query(int S, int X[], int T, int Y[]){
	vector<int> tab;
	for (int i = 0; i<S; i++)tab.push_back(X[i]);
	for (int i = 0; i<T; i++)tab.push_back(Y[i]);
	for (int i = 0; i<S; i++)fin[X[i]]=1;
	for (int i = 0; i<T; i++)fin[Y[i]]=2;
	sort(tab.begin(),tab.end(), [](int a, int b){return pre[a]<pre[b];});
	int powt=tab.size();
	for (int i = 0; i<powt-1; i++){
		if ((pre[tab[i+1]]-pre[tab[i]])*(post[tab[i+1]]-post[tab[i]])>=0){
			int dod=lca(tab[i],tab[i+1]);
			if (!fin[dod])tab.push_back(dod);
		}
	}
	sort(tab.begin(),tab.end(), [](int a, int b){return pre[a]<pre[b];});
	for (auto u : tab)dp[u][0]=dp[u][1]=oo;
	ll ans=oo;
	stack<int> st;
	st.push(tab[0]);
	for (int i = 1; i<tab.size(); i++){
		while(st.size() && post[st.top()]<post[tab[i]]){
			st.pop();
		}
		graph2[st.top()].push_back(tab[i]);
		st.push(tab[i]);
	}
	ans=dfs(tab[0]);
	for (auto u : tab)dp[u][0]=dp[u][1]=0;
	for (int i = 0; i<S; i++)fin[X[i]]=0;
	for (int i = 0; i<T; i++)fin[Y[i]]=0;
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for (int i = 1; i<tab.size(); i++){
      |                  ~^~~~~~~~~~~

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