oj.uz

Submission #780167

# Submission time Handle Problem Language Result Execution time Memory
780167 2023-07-12T07:05:42 Z SteGG Factories (JOI14_factories) C++17
100 / 100
 2076 ms 207556 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 26196 KB Output is correct
2 Correct 461 ms 35028 KB Output is correct
3 Correct 495 ms 35000 KB Output is correct
4 Correct 461 ms 35204 KB Output is correct
5 Correct 391 ms 35404 KB Output is correct
6 Correct 391 ms 34992 KB Output is correct
7 Correct 496 ms 35156 KB Output is correct
8 Correct 488 ms 35236 KB Output is correct
9 Correct 400 ms 35388 KB Output is correct
10 Correct 373 ms 35000 KB Output is correct
11 Correct 486 ms 35120 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26068 KB Output is correct
2 Correct 945 ms 161952 KB Output is correct
3 Correct 1136 ms 167392 KB Output is correct
4 Correct 701 ms 159496 KB Output is correct
5 Correct 946 ms 207556 KB Output is correct
6 Correct 1191 ms 168632 KB Output is correct
7 Correct 709 ms 60848 KB Output is correct
8 Correct 465 ms 59840 KB Output is correct
9 Correct 457 ms 67612 KB Output is correct
10 Correct 715 ms 61924 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 26196 KB Output is correct
2 Correct 461 ms 35028 KB Output is correct
3 Correct 495 ms 35000 KB Output is correct
4 Correct 461 ms 35204 KB Output is correct
5 Correct 391 ms 35404 KB Output is correct
6 Correct 391 ms 34992 KB Output is correct
7 Correct 496 ms 35156 KB Output is correct
8 Correct 488 ms 35236 KB Output is correct
9 Correct 400 ms 35388 KB Output is correct
10 Correct 373 ms 35000 KB Output is correct
11 Correct 486 ms 35120 KB Output is correct
12 Correct 14 ms 26068 KB Output is correct
13 Correct 945 ms 161952 KB Output is correct
14 Correct 1136 ms 167392 KB Output is correct
15 Correct 701 ms 159496 KB Output is correct
16 Correct 946 ms 207556 KB Output is correct
17 Correct 1191 ms 168632 KB Output is correct
18 Correct 709 ms 60848 KB Output is correct
19 Correct 465 ms 59840 KB Output is correct
20 Correct 457 ms 67612 KB Output is correct
21 Correct 715 ms 61924 KB Output is correct
22 Correct 1646 ms 172396 KB Output is correct
23 Correct 1673 ms 173184 KB Output is correct
24 Correct 2009 ms 177732 KB Output is correct
25 Correct 2076 ms 180820 KB Output is correct
26 Correct 1788 ms 171232 KB Output is correct
27 Correct 1790 ms 207216 KB Output is correct
28 Correct 1222 ms 167456 KB Output is correct
29 Correct 1816 ms 169740 KB Output is correct
30 Correct 1739 ms 169072 KB Output is correct
31 Correct 1728 ms 169708 KB Output is correct
32 Correct 682 ms 69320 KB Output is correct
33 Correct 581 ms 62448 KB Output is correct
34 Correct 702 ms 59744 KB Output is correct
35 Correct 688 ms 59344 KB Output is correct
36 Correct 757 ms 60484 KB Output is correct
37 Correct 853 ms 60480 KB Output is correct