제출 #903849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
903849		KN200711	공장들 (JOI14_factories)	C++14	100 / 100	7425 ms	173604 KiB

factories

#include "factories.h"
# include <bits/stdc++.h>
# define ll long long
# define ld long double
# define fi first
# define se second
# define pll pair<ll, ll>
# define pdd pair<ld, ld>
# define pii pair<int, int>
using namespace std;

vector<pii> edge[500001];
int in[500001], ot[500001], par[500001], sp[20][500001], dpt[500001], t, N1;
ll dist[500001], seg[2][2000001];

void dfs(int a, int pr, ll dis) {
	dist[a] = dis;
	in[a] = ++t;
	par[a] = pr;
	for(auto p : edge[a]) {
		if(p.fi == pr) continue;
		dpt[p.fi] = dpt[a] + 1;
		dfs(p.fi, a, dis + 1ll * p.se);
	}
	ot[a] = t;
}

void build_sp() {
	for(int i=0;i<20;i++) {
		for(int k=0;k<N1;k++) {
			if(i == 0) sp[i][k] = par[k];
			else sp[i][k] = sp[i - 1][sp[i - 1][k]];
		}
	}
}

int LCA(int a, int b) {
	if(dpt[a] < dpt[b]) swap(a, b);
	int sel = dpt[a] - dpt[b];
	for(int k=19;k>=0;k--) {
		if(sel&(1 << k)) {
			a = sp[k][a];
		}
	}
	if(a == b) return a;
	for(int k=19;k>=0;k--) {
		if(sp[k][a] != sp[k][b]) {
			a = sp[k][a];
			b = sp[k][b];
		}
	}
	return par[a];
}

void build(int lf, int rg, int nd) {
	seg[0][nd] = seg[1][nd] = 1e18;
	if(lf != rg) {
		int mid = (lf + rg) / 2;
		build(lf, mid, 2*nd + 1);
		build(mid+1, rg, 2*nd+2);
	}
}

void upd(int lf, int rg, int nd, int pos, int ty, ll val) {
	if(lf == rg) seg[ty][nd] = val;
	else {
		int mid = (lf + rg) / 2;
		if(pos <= mid) upd(lf, mid, 2*nd+1, pos, ty, val);
		else upd(mid+1, rg, 2*nd+2, pos, ty, val);
		seg[ty][nd] = min(seg[ty][2*nd+1], seg[ty][2*nd+2]);
	}
}

ll qry(int lf, int rg, int nd, int clf, int crg, int ty) {
	if(lf > crg || clf > rg) return 1e18;
	if(clf <= lf && rg <= crg) return seg[ty][nd];
	int mid = (lf + rg) / 2;
	return min(qry(lf, mid, 2*nd+1, clf, crg, ty), qry(mid+1, rg, 2*nd+2, clf, crg, ty));
}

void Init(int N, int A[], int B[], int D[]) {
	t = -1;
	N1 = N;
	for(int i=0;i<N-1;i++) {
		edge[A[i]].push_back(make_pair(B[i], D[i]));
		edge[B[i]].push_back(make_pair(A[i], D[i]));
	}
	dfs(0, -1, 0);
	build_sp();
//	cout<<"build sp"<<endl;
	build(0, N-1, 0);
//	cout<<"build"<<endl;
}

ll ans;

void cek(int a) {
//	cout<<"a : "<<a<<" "<<qry(0, N1-1, 0, in[a], ot[a], 0)<<" "<<qry(0, N1-1, 0, in[a], ot[a], 1)<<" "<<dist[a]<<endl;
	ll d = qry(0, N1-1, 0, in[a], ot[a], 0) + qry(0, N1-1, 0, in[a], ot[a], 1) - 2ll * dist[a];
	ans = min(ans, d);
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<pii> arr;
	arr.clear();
	for(int i=0;i<S;i++) {
		upd(0, N1 - 1, 0, in[X[i]], 0, dist[X[i]]);
		arr.push_back({in[X[i]], X[i]});
	}
	for(int i=0;i<T;i++) {
		upd(0, N1-1, 0, in[Y[i]], 1, dist[Y[i]]);
		arr.push_back({in[Y[i]], Y[i]});
	}
	sort(arr.begin(), arr.end());
	ans = 1e18;
	for(int i=0;i<arr.size();i++) {
		cek(arr[i].se);
		if(i + 1 < arr.size()) {
			cek(LCA(arr[i].se, arr[i + 1].se));
		}
	}
	for(int i=0;i<S;i++) {
		upd(0, N1 - 1, 0, in[X[i]], 0, 1e18);
	}
	for(int i=0;i<T;i++) {
		upd(0, N1-1, 0, in[Y[i]], 1, 1e18);
	}
	return ans;
}

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

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

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