oj.uz

Submission #532802

# Submission time Handle Problem Language Result Execution time Memory
532802 2022-03-04T00:41:06 Z Leonardo_Paes Factories (JOI14_factories) C++17
100 / 100
 6878 ms 212232 KB 
#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 = 20;
const ll inf = 1e18;

vector<pii> tree[maxn], grafo[maxn];
int n, tt, in[maxn], out[maxn], nivel[maxn], sz[maxn], mn[2*maxn][maxl];
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;
	mn[tt][0] = u;
	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;
		dfs_lca(v, u);
		mn[++tt][0] = u;
	}
}

int lca(int u, int v){
	if(in[u] > in[v]) swap(u, v);
	int l = in[u], r = in[v], len = r-l+1, p = 31-__builtin_clz(len-1);
	return nivel[mn[l][p]] < nivel[mn[r-(1<<p)][p]] ? mn[l][p] : mn[r-(1<<p)][p];
}

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<=2*n; i++){
			mn[i][j] = nivel[mn[i][j-1]] < nivel[mn[min(2*n-1, i+(1<<(j-1)))][j-1]] ?
			mn[i][j-1] : mn[min(2*n-1, i+(1<<(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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 24332 KB Output is correct
2 Correct 1254 ms 37108 KB Output is correct
3 Correct 1627 ms 36968 KB Output is correct
4 Correct 1532 ms 37140 KB Output is correct
5 Correct 1324 ms 37320 KB Output is correct
6 Correct 538 ms 36976 KB Output is correct
7 Correct 1639 ms 37100 KB Output is correct
8 Correct 1501 ms 37140 KB Output is correct
9 Correct 1303 ms 37332 KB Output is correct
10 Correct 533 ms 36988 KB Output is correct
11 Correct 1610 ms 37016 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24140 KB Output is correct
2 Correct 1555 ms 169108 KB Output is correct
3 Correct 1901 ms 170304 KB Output is correct
4 Correct 1158 ms 163536 KB Output is correct
5 Correct 1548 ms 205264 KB Output is correct
6 Correct 2001 ms 171880 KB Output is correct
7 Correct 2032 ms 65196 KB Output is correct
8 Correct 828 ms 64456 KB Output is correct
9 Correct 1195 ms 70876 KB Output is correct
10 Correct 1861 ms 66268 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 24332 KB Output is correct
2 Correct 1254 ms 37108 KB Output is correct
3 Correct 1627 ms 36968 KB Output is correct
4 Correct 1532 ms 37140 KB Output is correct
5 Correct 1324 ms 37320 KB Output is correct
6 Correct 538 ms 36976 KB Output is correct
7 Correct 1639 ms 37100 KB Output is correct
8 Correct 1501 ms 37140 KB Output is correct
9 Correct 1303 ms 37332 KB Output is correct
10 Correct 533 ms 36988 KB Output is correct
11 Correct 1610 ms 37016 KB Output is correct
12 Correct 15 ms 24140 KB Output is correct
13 Correct 1555 ms 169108 KB Output is correct
14 Correct 1901 ms 170304 KB Output is correct
15 Correct 1158 ms 163536 KB Output is correct
16 Correct 1548 ms 205264 KB Output is correct
17 Correct 2001 ms 171880 KB Output is correct
18 Correct 2032 ms 65196 KB Output is correct
19 Correct 828 ms 64456 KB Output is correct
20 Correct 1195 ms 70876 KB Output is correct
21 Correct 1861 ms 66268 KB Output is correct
22 Correct 4595 ms 179388 KB Output is correct
23 Correct 3420 ms 179172 KB Output is correct
24 Correct 6878 ms 183356 KB Output is correct
25 Correct 6038 ms 188828 KB Output is correct
26 Correct 5005 ms 180420 KB Output is correct
27 Correct 5126 ms 212232 KB Output is correct
28 Correct 2015 ms 181396 KB Output is correct
29 Correct 4385 ms 179648 KB Output is correct
30 Correct 4286 ms 178984 KB Output is correct
31 Correct 4176 ms 179712 KB Output is correct
32 Correct 2440 ms 83724 KB Output is correct
33 Correct 1048 ms 82204 KB Output is correct
34 Correct 2313 ms 74424 KB Output is correct
35 Correct 2138 ms 74260 KB Output is correct
36 Correct 3031 ms 75232 KB Output is correct
37 Correct 2927 ms 75024 KB Output is correct