Submission #532766

#	Time	Username	Problem	Language	Result	Execution time	Memory
532766		Leonardo_Paes	Factories (JOI14_factories)	C++17	33 / 100	8021 ms	186548 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
typedef pair<ll,int> porra;
typedef pair<ll,ll> pll;
#define f first
#define s second
const int maxn = 5e5+10, maxl = 21;
const ll inf = 1e18;

vector<pii> tree[maxn], grafo[maxn];
int n, tt, in[maxn], tab[maxn][maxl], nivel[maxn], sz[maxn];
vector<int> limpa;
ll dist[maxn], ans;
bool red[maxn], blue[maxn], mark[maxn];

void dfs_lca(int u, int p = 0){
	in[u] = tt++;
	for(pii vv : tree[u]){
		int v = vv.f;
		ll d = vv.s;
		if(v == p) continue;
		nivel[v] = nivel[u] + 1;
		dist[v] = dist[u] + d;
		tab[v][0] = u;
		dfs_lca(v, u);
	}
}

int lca(int u, int v){
	if(u == v) return u;
	if(nivel[u] < nivel[v]) swap(u, v);
	for(int i=maxl-1; i>=0; i--){
		if(nivel[tab[u][i]] >= nivel[v]) u = tab[u][i];
	}
	if(u == v) return u;
	for(int i=maxl-1; i>=0; i--){
		if(tab[u][i] and tab[u][i] != tab[v][i]){
			u = tab[u][i], v = tab[v][i];
		}
	}
	return tab[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i=0; i<n-1; i++){
		int u = A[i] + 1, v = B[i] + 1, d = D[i];
		tree[u].push_back({v, d});
		tree[v].push_back({u, d});
	}
	nivel[1] = 1;
	dfs_lca(1);
	for(int j=1; j<maxl; j++){
		for(int i=1; i<=n; i++){
			tab[i][j] = tab[tab[i][j-1]][j-1];
		}
	}
}

void virtual_tree(vector<int> &k){
	auto comp = [&](int u, int v){
		return in[u] < in[v];
	};
	sort(k.begin(), k.end(), comp);
	int tam = k.size();
	for(int i=1; i<tam; i++) k.push_back(lca(k[i-1], k[i]));
	sort(k.begin(), k.end(), comp);
	k.erase(unique(k.begin(), k.end()), k.end());
	for(int i=0; i<k.size(); i++){
		limpa.push_back(k[i]);
		if(!i) continue;
		int l = lca(k[i-1], k[i]);
		ll w = dist[k[i]] - dist[l];
		//cout << "adicionando aresta: " << l << " " << k[i] << " " << w << "\n";
		grafo[l].push_back({k[i], w});
		grafo[k[i]].push_back({l, w});
	}
}

void dfs(int u, int p = 0){
	sz[u] = 1;
	for(pii vv : grafo[u]){
		int v = vv.f;
		if(v == p or mark[v]) continue;
		dfs(v, u);
		sz[u] += sz[v];
	}
}

int centroid(int u, int siz, int p = 0){
	for(pii vv : grafo[u]){
		int v = vv.f;
		if(v == p or mark[v]) continue;
		if(sz[v] + sz[v] > siz) return centroid(v, siz, u);
	}
	return u;
}

pll aux;

void solve(int u, ll d, int p){
	if(red[u]) aux.f = min(aux.f, d);
	if(blue[u]) aux.s = min(aux.s, d);
	for(pii vv : grafo[u]){
		int v = vv.f;
		ll dis = d + vv.s;
		if(v == p or mark[v]) continue;
		solve(v, dis, u);
	}
}

void decompose(int u){
	dfs(u);
	int c = centroid(u, sz[u]);
	mark[c] = 1;
	porra mnblue[2], mnred[2];
	for(int i=0; i<2; i++) mnblue[i] = mnred[i] = {inf, 0};
	if(red[c]) mnred[0] = {0, -1};
	if(blue[c]) mnblue[0] = {0, -1};
	vector<array<ll,3>> wtf;
	for(pii vv : grafo[c]){
		int v = vv.f;
		ll d = vv.s;
		if(mark[v]) continue;
		aux = {inf, inf};
		solve(v, d, c);
		if(aux.f <= mnred[0].f){
			mnred[1] = mnred[0];
			mnred[0] = {aux.f, v};
		}
		else if(aux.f <= mnred[1].f) mnred[1] = {aux.f, v};
		if(aux.s <= mnblue[0].f){
			mnblue[1] = mnblue[0];
			mnblue[0] = {aux.s, v};
		}
		else if(aux.s <= mnblue[1].f) mnblue[1] = {aux.s, v};
		wtf.push_back({v, aux.f, aux.s});
	}
	for(auto x : wtf){
		ll u = x[0], r = x[1], b = x[2];
		if(mnred[0].s == u) ans = min(ans, mnred[1].f + b);
		else ans = min(ans, mnred[0].f + b);
		if(mnblue[0].s == u) ans = min(ans, mnblue[1].f + r);
		else ans = min(ans, mnblue[0].f + r);	
	}
	for(pii viz : grafo[c]){
		int v = viz.f;
		if(mark[v]) continue;
		decompose(v);
	}
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<int> k;
	for(int i=0; i<S; i++){
		++X[i];
		k.push_back(X[i]);
		red[X[i]] = 1;
	}
	for(int i=0; i<T; i++){
		++Y[i];
		k.push_back(Y[i]);
		blue[Y[i]] = 1;
	}
	virtual_tree(k);
	ans = inf;
	decompose(limpa[0]);
	for(int i : limpa){
		grafo[i].clear();
		mark[i] = 0;
		sz[i] = 0;
	}
	limpa.clear();
	for(int i=0; i<S; i++) red[X[i]] = 0;
	for(int i=0; i<T; i++) blue[Y[i]] = 0;
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void virtual_tree(std::vector<int>&)':
factories.cpp:72:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i=0; i<k.size(); i++){
      |               ~^~~~~~~~~

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