Submission #780167

#	Time	Username	Problem	Language	Result	Execution time	Memory
780167		SteGG	Factories (JOI14_factories)	C++17	100 / 100	2076 ms	207556 KiB

factories

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

using namespace std;

const int maxn = 5e5 + 5;
const int base = 32;
const long long inf = 3e18 + 5;

vector<pair<int, long long>> tr[maxn];
int tin[maxn],tout[maxn];
int tour[2*maxn + 5];
int timer = 0;
vector<pair<int, long long>> virtual_tr[maxn];
int ty[maxn];
long long road0[maxn], road1[maxn], d[maxn];
int lg[2 * maxn + 5];

int custom_min(int a, int b){
	if(d[a] < d[b]) return a;
	return b;
}

struct SpareTable{
	int table[base][2*maxn + 5];

	void assign(){
		build();
		init_lg();
	}

	void build(){
		for(int i = 1; i <= timer; i++){
			table[0][i] = tour[i];
		}

		for(int i = 1; i < base; i++){
			for(int j = 1; j + (1LL << i) - 1 <= timer; j++){
				table[i][j] = custom_min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
			}
		}
	}

	void init_lg(){
		for(int i = 2; i <= timer; i++){
			lg[i] = lg[i / 2] + 1;
		}
	}

	int get(int l, int r){
		int len = r - l + 1;
		int layer = lg[len];
		return custom_min(table[layer][l], table[layer][r - (1 << layer) + 1]);
	}
};

SpareTable sp;

void dfs(int u, int p){
	tin[u] = ++timer;
	tour[timer] = u;
	for(pair<int, long long> node : tr[u]){
		int v = node.first;
		long long w = node.second;
		if(v == p) continue;
		d[v] = d[u] + w;
		dfs(v, u);
		tour[++timer] = u;
	}
	tout[u] = timer;
}

bool isparent(int u, int v){ // u is parent of v
	if(tin[u] < tin[v] && tout[v] < tout[u]) return true;
	return false;
}

int lca(int u, int v){
	if(isparent(u, v)) return u;
	else if(isparent(v, u)) return v;
	else{
		if(tin[u] > tout[v]) return sp.get(tout[v], tin[u]);
		else return sp.get(tout[u], tin[v]);
	}
}

long long dist(int u, int v){
	int c = lca(u, v);
	return (d[u] - d[c]) + (d[v] - d[c]);
}

void Init(int N, int A[], int B[], int D[]){
	for(int i = 0; i < N - 1; i++){
		int a = A[i];
		int b = B[i];
		int d = D[i];
		tr[a].push_back({b, d});
		tr[b].push_back({a, d});
	}
	dfs(0, -1);
	sp.assign();
	memset(ty, -1, sizeof(ty));
}

void solve(int u, int p){
	for(auto node : virtual_tr[u]){
		int v = node.first;
		long long w = node.second;
		if(v == p) continue;
		solve(v, u);
		road0[u] = min(road0[u], road0[v] + w);
		road1[u] = min(road1[u], road1[v] + w);
	}
}

long long Query(int S, int X[], int T, int Y[]){
	vector<int> temp;
	int sz_temp = S + T;

	for(int i = 0; i < S; i++){
		ty[X[i]] = 0;
		road0[X[i]] = inf;
		road1[X[i]] = 0;
		temp.push_back(X[i]);
	}

	for(int i = 0; i < T; i++){
		if(ty[Y[i]] == 0) return 0;
		ty[Y[i]] = 1;
		road0[Y[i]] = 0;
		road1[Y[i]] = inf;
		temp.push_back(Y[i]);
	}

	sort(temp.begin(), temp.end(), [&](int a, int b){
		return tin[a] < tin[b];
	});

	for(int i = 1; i < sz_temp; i++){
		int c = lca(temp[i], temp[i - 1]);
		if(ty[c] == -1){
			ty[c] = 2;
			road0[c] = road1[c] = inf;
			temp.push_back(c);
		}
	}

	temp.resize(unique(temp.begin(), temp.end()) - temp.begin());

	sort(temp.begin(), temp.end(), [&](int a, int b){
		return tin[a] < tin[b];
	});

	stack<int> stk;

	for(int i = 0; i < temp.size(); i++){
		if(stk.empty()){
			stk.push(temp[i]);
			continue;
		}
		while(!stk.empty() && !isparent(stk.top(), temp[i])){
			stk.pop();
		}

		if(!stk.empty()){
			virtual_tr[stk.top()].push_back({temp[i], dist(stk.top(), temp[i])});
		}

		stk.push(temp[i]);
	}

	solve(temp[0], -1);
	long long result = inf;

	for(int i = 0; i < temp.size(); i++){
		result = min(result, road0[temp[i]] + road1[temp[i]]);
		ty[temp[i]] = -1;
		virtual_tr[temp[i]].clear();
	}

	return result;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:156:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |  for(int i = 0; i < temp.size(); i++){
      |                 ~~^~~~~~~~~~~~~
factories.cpp:175:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |  for(int i = 0; i < temp.size(); i++){
      |                 ~~^~~~~~~~~~~~~

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