oj.uz

Submission #879131

# Submission time Handle Problem Language Result Execution time Memory
879131 2023-11-26T12:07:52 Z serifefedartar Factories (JOI14_factories) C++17
0 / 100
 10 ms 35420 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 5e5 + 100;

vector<vector<pair<int,int>>> graph;
int marked[MAXN], sz[MAXN];
ll ans[MAXN];
vector<pair<int,ll>> anc[MAXN];

int get_sz(int node, int parent) {
	sz[node] = 1;
	for (auto u : graph[node]) {
		if (u.f == parent || marked[u.f])
			continue;
		sz[node] += get_sz(u.f, node);
	}
	return sz[node];
}

int find_centro(int node, int parent, int n) {
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f] && sz[u.f] * 2 > n)
			return find_centro(u.f, node, n);	
	}
	return node;
}

void dfs(int node, int parent, int centro, ll dist) {
	for (auto u : graph[node]) {
		if (u.f == parent || marked[u.f]) 
			continue;
		dfs(u.f, node, centro, dist + u.s);
	}
	anc[node].push_back({centro, dist});
}

void decompose(int node, int parent) {
	int n = get_sz(node, node);
	int centro = find_centro(node, node, n);

	marked[centro] = true;
	anc[centro].push_back({centro, 0});
	for (auto u : graph[centro]) {
		if (!marked[u.f])
			dfs(u.f, centro, centro, 0);
	}

	for (auto u : graph[centro]) {
		if (!marked[u.f])
			decompose(u.f, centro);
	}
}

void Init(int N, int A[], int B[], int D[]) {
	graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
	for (int i = 0; i < N-1; i++) {
		graph[A[i] + 1].push_back({B[i] + 1, D[i]});
		graph[B[i] + 1].push_back({A[i] + 1, D[i]});
	}
	decompose(1, -1);

	for (int i = 0; i < MAXN; i++)
		ans[i] = 1e15;
}

void add(int node) {
	for (auto u : anc[node])
		ans[u.f] = min(ans[u.f], u.s);
}

void remove(int node) {
	for (auto u : anc[node])
		ans[u.f] = 1e15;
}

ll qry(int node) {
	ll res = 1e15;
	for (auto u : anc[node])
		res = min(res, u.s + ans[u.f]);
	return res;
}

ll Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++)
		add(X[i] + 1);

	ll mn = 1e15;
	for (int i = 0; i < T; i++)
		mn = min(mn, qry(Y[i] + 1));

	for (int i = 0; i < S; i++)
		remove(X[i] + 1);
	return mn;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 35420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 35420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 35420 KB Output isn't correct
2 Halted 0 ms 0 KB -