제출 #117661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117661		kig9981	공장들 (JOI14_factories)	C++17	100 / 100	6650 ms	115960 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

vector<pair<int,int>> adj[500000];
int query_num, root, depth[500000], parent[500000], P[500000], W[500000], hld[500000], num[500000];
long long dist[500000], V[500000];
bool chk[500000];

int set_weight(int c)
{
	W[c]=1;
	for(auto[n,w]: adj[c]) if(W[n]==0) {
		depth[n]=depth[c]+1;
		dist[n]=dist[c]+w;
		parent[n]=c;
		W[c]+=set_weight(n);
	}
	return W[c];
}

void set_hld(int c)
{
	for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]>=W[c]) {
		hld[n]=hld[c];
		set_hld(n);
	}
	for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]<W[c]) {
		hld[n]=n;
		set_hld(n);
	}
}

int LCA(int a, int b)
{
	while(hld[a]!=hld[b]) {
		if(depth[hld[a]]<depth[hld[b]]) b=parent[hld[b]];
		else a=parent[hld[a]];
	}
	return depth[a]<depth[b] ? a:b;
}

void reset_weight(int c)
{
	W[c]=0;
	for(auto[n,w]: adj[c]) if(!chk[n] && W[n]) reset_weight(n);
}

int set_weight2(int c)
{
	W[c]=1;
	for(auto[n,w]: adj[c]) if(!chk[n] && W[n]==0) W[c]+=set_weight2(n);
	return W[c];
}

int get_mid(int c, int r)
{
	bool valid=true;
	int t;
	if(W[r]>2*W[c]) valid=false;
	for(auto[n,w]: adj[c]) if(!chk[n] && W[n]<W[c]) {
		if((t=get_mid(n,r))!=-1) return t;
		if(2*W[n]>W[r]) valid=false;
	}
	return valid ? c:-1;
}

int get_centroid(int c)
{
	reset_weight(c), set_weight2(c);
	chk[c=get_mid(c,c)]=true;
	for(auto[n,w]: adj[c]) if(!chk[n]) P[get_centroid(n)]=c;
	return c;
}

void Init(int N, int *A, int *B, int *D)
{
	for(int i=0;i<N-1;i++) {
		adj[A[i]].emplace_back(B[i],D[i]);
		adj[B[i]].emplace_back(A[i],D[i]);
	}
	set_weight(0); set_hld(0);
	root=get_centroid(0);
}

long long Query(int S, int *X, int T, int *Y)
{
	long long ret=0x7fffffffffffffffLL;
	query_num++;
	for(int i=0;i<S;i++) {
		for(int j=X[i];j!=root;j=P[j]) {
			if(num[j]==query_num) V[j]=min(V[j],dist[X[i]]+dist[j]-2*dist[LCA(X[i],j)]);
			else {
				num[j]=query_num;
				V[j]=dist[X[i]]+dist[j]-2*dist[LCA(X[i],j)];
			}
		}
		if(num[root]==query_num) V[root]=min(V[root],dist[X[i]]+dist[root]-2*dist[LCA(X[i],root)]);
		else {
			num[root]=query_num;
			V[root]=dist[X[i]]+dist[root]-2*dist[LCA(X[i],root)];
		}
	}
	for(int i=0;i<T;i++) {
		for(int j=Y[i];j!=root;j=P[j]) {
			if(num[j]!=query_num) continue;
			ret=min(ret,V[j]+dist[Y[i]]+dist[j]-2*dist[LCA(Y[i],j)]);
		}
		ret=min(ret,V[root]+dist[Y[i]]+dist[root]-2*dist[LCA(Y[i],root)]);
	}
	return ret;
}

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

factories.cpp: In function 'void set_hld(int)':
factories.cpp:25:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]>=W[c]) {
              ^
factories.cpp:29:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]<W[c]) {
              ^
factories.cpp: In function 'void reset_weight(int)':
factories.cpp:47:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) if(!chk[n] && W[n]) reset_weight(n);
              ^
factories.cpp: In function 'int set_weight2(int)':
factories.cpp:53:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) if(!chk[n] && W[n]==0) W[c]+=set_weight2(n);
              ^
factories.cpp: In function 'int get_mid(int, int)':
factories.cpp:62:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) if(!chk[n] && W[n]<W[c]) {
              ^
factories.cpp: In function 'int get_centroid(int)':
factories.cpp:73:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) if(!chk[n]) P[get_centroid(n)]=c;
              ^

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