oj.uz

Submission #780052

# Submission time Handle Problem Language Result Execution time Memory
780052 2023-07-12T06:10:32 Z SteGG Factories (JOI14_factories) C++17
15 / 100
 949 ms 160492 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

const int maxn = 5e5 + 5;
const int base = 32;
const long long inf = 1e15;

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 custom_min(int a, int b){
	if(d[a] < d[b]) return a;
	return b;
}

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

	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[v] - 2*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 508 ms 35028 KB Output is correct
3 Correct 512 ms 35012 KB Output is correct
4 Correct 487 ms 35108 KB Output is correct
5 Correct 412 ms 35992 KB Output is correct
6 Correct 393 ms 35504 KB Output is correct
7 Correct 501 ms 35668 KB Output is correct
8 Correct 510 ms 35636 KB Output is correct
9 Correct 430 ms 35896 KB Output is correct
10 Correct 444 ms 35500 KB Output is correct
11 Correct 510 ms 35556 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26068 KB Output is correct
2 Incorrect 949 ms 160492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 26196 KB Output is correct
2 Correct 508 ms 35028 KB Output is correct
3 Correct 512 ms 35012 KB Output is correct
4 Correct 487 ms 35108 KB Output is correct
5 Correct 412 ms 35992 KB Output is correct
6 Correct 393 ms 35504 KB Output is correct
7 Correct 501 ms 35668 KB Output is correct
8 Correct 510 ms 35636 KB Output is correct
9 Correct 430 ms 35896 KB Output is correct
10 Correct 444 ms 35500 KB Output is correct
11 Correct 510 ms 35556 KB Output is correct
12 Correct 15 ms 26068 KB Output is correct
13 Incorrect 949 ms 160492 KB Output isn't correct
14 Halted 0 ms 0 KB -