제출 #1048375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1048375		tamir1	Factories (JOI14_factories)	C++17	0 / 100	8074 ms	122600 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
ll dis[100010];
int jump[23][100010],dep[100010];
vector<pair<int,ll>> v[100010]; 
void dfs(int x,int y){
	int nx;
	ll len;
	jump[0][x]=y;
	for(int i=0;i<v[x].size();i++){
		nx=v[x][i].ff;
		if(nx==y) continue;
		len=v[x][i].ss;
		dep[nx]=dep[x]+1;
		dis[nx]=dis[x]+len;
		dfs(nx,x);
	}
}
int up(int x,int k){
	for(int i=0;i<=20;i++){
		if(k&(1<<i)) x=jump[i][x];
	}
	return x;
}
int lca(int x,int y){
	if(dep[x]>dep[y]) swap(x,y);
	y=up(y,dep[y]-dep[x]);
	if(x==y) return x;
	for(int i=20;i>=0;i--){
		if(jump[i][x]!=jump[i][y]){
			x=jump[i][x];
			y=jump[i][y];
		}
	}
	return jump[0][x];
}

void Init(int N, int A[], int B[], int D[]) {
	for(int i=0;i<N-1;i++){
		v[A[i]].push_back({B[i],D[i]});
		v[B[i]].push_back({A[i],D[i]});
	}
	dfs(0,0);
	for(int j=1;j<=20;j++){
		for(int i=0;i<N;i++){
			jump[j][i]=jump[j-1][jump[j-1][i]];
		}
	}
}
long long Query(int S, int X[], int T, int Y[]) {
	ll res=1e18;
	for(int i=0;i<S;i++){
		for(int j=0;j<T;j++){
			ll b=dis[X[i]]+dis[Y[j]]-2*dis[lca(X[i],Y[j])];
			res=min(res,b);
		}
	}
	return res;
}

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

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~

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