제출 #364910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364910		ogibogi2004	공장들 (JOI14_factories)	C++14	33 / 100	8053 ms	401484 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e17;
const int MAXN=2e6+6;
const int lg=23;
ll ans;
vector<pair<int,ll> >g[MAXN];
vector<int>g1[MAXN];
int par[MAXN];
pair<int,int> dp[2*MAXN][lg];
int depth[MAXN];
ll depth1[MAXN];
int pw[2*MAXN],n;
int wherel[MAXN],wherer[MAXN];
vector<int>dfs_order;
int st[MAXN];
bool f[MAXN];
ll mind[MAXN];
void dfs1(int u,int p)
{
	dfs_order.push_back(u);
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		depth1[v.first]=depth1[u]+v.second;
		depth[v.first]=depth[u]+1;
		dfs1(v.first,u);
		dfs_order.push_back(u);
	}
}
void precompute()
{
	int t=1,c=0;
	for(int i=1;i<=MAXN;i++)
	{
		if(t*2<=i)
		{
			t*=2;c++;
		}
		pw[i]=c;
	}
	for(int i=0;i<dfs_order.size();i++)
	{
		dp[i][0]={depth[dfs_order[i]],dfs_order[i]};
	}
	for(int i=0;i<dfs_order.size();i++)
	{
		wherer[dfs_order[i]]=i;
	}
	
	for(int i=dfs_order.size()-1;i>=0;i--)
	{
		wherel[dfs_order[i]]=i;
	}
	for(int step=1;step<lg;step++)
	{
		for(int i=0;i<dfs_order.size();i++)
		{
			dp[i][step]=dp[i][step-1];
			if(i+(1<<(step-1))<dfs_order.size())
			{
				dp[i][step]=min(dp[i][step],dp[i+(1<<(step-1))][step-1]);
			}
		}
	}
}
int lca(int x,int y)
{
	if(wherel[x]>wherel[y])swap(x,y);
	int i1=wherel[x];
	int i2=wherer[y];
	int d=i2-i1+1;
	int t=pw[d];
	pair<int,int>ret=dp[i1][t];
	ret=min(ret,dp[i2-(1<<t)+1][t]);
	return ret.second;
}
ll dist(int x,int y)
{
	return depth1[x]+depth1[y]-2*depth1[lca(x,y)];
}
void dfs2(int u,int p)
{
	st[u]=1;
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(f[v.first])continue;
		dfs2(v.first,u);
		st[u]+=st[v.first];
	}
}
int find(int u,int p,int t)
{
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(f[v.first])continue;
		if(st[v.first]>t/2)return find(v.first,u,t);
	}
	return u;
}
void decompose(int u,int p)
{
	dfs2(u,p);
	int c=find(u,p,st[u]);
	if(p>0)
	{
		g1[p].push_back(c);
	}
	par[c]=p;
	f[c]=1;
	for(auto v:g[c])
	{
		if(f[v.first])continue;
		decompose(v.first,c);
	}
}
void Init(int N, int A[], int B[], int D[]) {
	n=N;
	for(int i=0;i<n-1;i++)
	{
		g[A[i]+1].push_back({B[i]+1,D[i]});
		g[B[i]+1].push_back({A[i]+1,D[i]});
	}
	dfs1(1,0);
	precompute();
	decompose(1,-1);
	for(int i=0;i<MAXN;i++)mind[i]=INF;
}
void update(int x)
{
	mind[x]=0;
	int y=par[x];
	while(y>0)
	{
		mind[y]=min(mind[y],dist(x,y));
		y=par[y];
	}
}
void clear(int x)
{
	mind[x]=INF;
	int y=par[x];
	while(y>0)
	{
		mind[y]=INF;
		y=par[y];
	}
}
void check(int x)
{
	ans=min(ans,mind[x]);
	int y=par[x];
	while(y>0)
	{
		ans=min(ans,mind[y]+dist(x,y));
		y=par[y];
	}
}
long long Query(int S, int X[], int T, int Y[]) {
	ans=INF;
	for(int i=0;i<S;i++)
	{
		update(X[i]+1);
	}
	for(int i=0;i<T;i++)
	{
		check(Y[i]+1);
	}
	for(int i=0;i<S;i++)
	{
		clear(X[i]+1);
	}
	return ans;
}

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

factories.cpp: In function 'void precompute()':
factories.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<dfs_order.size();i++)
      |              ~^~~~~~~~~~~~~~~~~
factories.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<dfs_order.size();i++)
      |              ~^~~~~~~~~~~~~~~~~
factories.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int i=0;i<dfs_order.size();i++)
      |               ~^~~~~~~~~~~~~~~~~
factories.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    if(i+(1<<(step-1))<dfs_order.size())
      |       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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