답안 #25324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25324	2017-06-21T07:13:20 Z	서규호(#1060)	공장들 (JOI14_factories)	C++14	컴파일 오류	0 ms	0 KB

factories

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

#define pb push_back
#define lld long long
#define Linf 1000000000000000000LL

using namespace std;

int N; lld ans;
int lev[500002];
pair<int,lld> par[500002][20];
int color[500002];
bool check[500002];
vector<pair<int,lld>> edge[500002];

void makepar(int x){
	check[x] = true;
	for(auto &i : edge[x]){
		if(check[i.first]) continue;
		lev[i.first] = lev[x]+1;
		par[i.first][0].first = x; par[i.first][0].second = i.second;
		for(int j=1; j<=19; j++){
			par[x][j].first = par[par[x][j-1].first][j-1].first;
			par[x][j].second = par[par[x][j-1].first][j-1].second+par[x][j-1].second;
		}
		makepar(i.first);
	}
}

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

pair<lld,lld> dfs(int x){
	check[x] = true;
	pair<lld,lld> tmp = {Linf,Linf};
	if(color[x] == 1) tmp.first = 0;
	else if(color[x] == 2) tmp.second = 0;
	for(auto &i : edge[x]){
		if(check[i.first]) continue;
		pair<lld,lld> t = dfs(i.first);
		t.first += i.second; t.second += i.second;
		ans = min(ans,tmp.first+t.second);
		ans = min(ans,tmp.second+t.first);
		tmp.first = min(tmp.first,t.first);
		tmp.second= min(tmp.second,t.second);
	}
	return tmp;
}

int getpar(int x,int y){
	if(lev[x] > lev[y]) swap(x,y);
	for(int i=0; i<=19; i++){
		if(((lev[y]-lev[x])&(1<<i)) == 0) continue;
		y = par[y][i].first;
	}
	if(x == y) return x;
	int t;
	for(int i=0; i<=19; i++){
		if(par[x][i] == par[y][i]){
			t = i;
			break;
		}
	}
	while(t){
		t--;
		if(par[x][t] != par[y][t]){
			x = par[x][t].first;
			y = par[y][t].first;
		}
	}
	return par[x][0];
}
lld getdis(int x,int y){
	lld tsum = 0;
	for(int i=0; i<=19; i++){
		if(((lev[y]-lev[x])&(1<<i)) == 0) continue;
		tsum += par[y][i].second;
		y = par[y][i].first;
	}
}

lld Query(int S, int X[], int T, int Y[]) {
	if(S <= 10 && T <= 10){
		ans = Linf;
		for(int i=0; i<S; i++){
			for(int j=0; j<T; j++){
				int tmp = getpar(X[i+1],Y[i+1]);
				ans = min(ans,getdis(X[i+1],tmp)+getdis(Y[i+1],tmp));
			}
		}
		return ans;
	}
	for(int i=1; i<=N; i++){
		color[i] = 0;
		check[i] = false;
	}
	for(int i=0; i<S; i++) color[X[i]+1] = 1;
	for(int i=0; i<T; i++) color[Y[i]+1] = 2;
	ans = Linf;
	dfs(1);
	return ans;
}

Compilation message

factories.cpp: In function 'int getpar(int, int)':
factories.cpp:79:17: error: cannot convert 'std::pair<int, long long int>' to 'int' in return
  return par[x][0];
                 ^
factories.cpp: In function 'long long int getdis(int, int)':
factories.cpp:88:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^