oj.uz

답안 #886253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886253 2023-12-11T15:56:43 Z javotaz 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 411256 KB 
// In the Name of Allah
 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 5e5 + 12, inf = 1e18 + 12;
vector<pair<int, int>> g[N];
int sz[N], cpar[N], q, n;
ll val[N];
set<pair<int, ll>> cdis[N];
bool mrk[N];

void dfs(int u, int par = -1) {
	sz[u] = 1;
	for (auto i: g[u])
		if (i.first != par && !mrk[i.first]) {
			dfs(i.first, u);
			sz[u] += sz[i.first];
		}
}

int find_centroid(int u, int c, int par = -1) {
	for (auto i: g[u])
		if (!mrk[i.first] && i.first != par && sz[i.first] > (c - 1) / 2)
			return find_centroid(i.first, c, u);
	return u;
}

void fill_cdis(int u, int cent, ll c = 0, int par = -1) {
	cdis[cent].insert({u, c});
	for (auto i: g[u])
		if (!mrk[i.first] && i.first != par)
			fill_cdis(i.first, cent, c + i.second, u);
}

void decompose(int u, int par = -1) {
	dfs(u);
	u = find_centroid(u, sz[u]);
	fill_cdis(u, u);
	cpar[u] = par;
	mrk[u] = true;
	for (auto i: g[u])
		if (!mrk[i.first])
			decompose(i.first, u);
}

void add(int u, int v) {
	if (u == -1)
		return;
	val[u] = min(val[u], cdis[u].lower_bound({v, -1})->second);
	add(cpar[u], v);
}

ll ask(int u, int v) {
	if (u == -1)
		return inf;
	ll tmp = cdis[u].lower_bound({v, -1})->second;
	return min(ask(cpar[u], v), tmp + val[u]);
}

void rem(int u) {
	val[u] = inf;
	if (cpar[u] != -1)
		rem(cpar[u]);
}

void Init(int c, int a[], int b[], int d[]) {
	n = c;
	for (int i = 0; i < n - 1; i++) {
		g[a[i]].push_back({b[i], d[i]});
		g[b[i]].push_back({a[i], d[i]});
	}
	decompose(0);
	fill(val, val + n, inf);
}

ll Query(int s, int x[], int t, int y[]) {
	for (int i = 0; i < s; i++)
		add(x[i], x[i]);
	ll res = inf;
	for (int i = 0; i < t; i++)
		res = min(res, ask(y[i], y[i]));
	for (int i = 0; i < s; i++)
		rem(x[i]);
	return res;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 59988 KB Output is correct
2 Correct 1141 ms 66388 KB Output is correct
3 Correct 1782 ms 67412 KB Output is correct
4 Correct 1784 ms 67348 KB Output is correct
5 Correct 2103 ms 68112 KB Output is correct
6 Correct 345 ms 64852 KB Output is correct
7 Correct 1814 ms 67344 KB Output is correct
8 Correct 1776 ms 67264 KB Output is correct
9 Correct 2185 ms 68180 KB Output is correct
10 Correct 348 ms 64776 KB Output is correct
11 Correct 1770 ms 67388 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 59996 KB Output is correct
2 Execution timed out 8096 ms 411256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 59988 KB Output is correct
2 Correct 1141 ms 66388 KB Output is correct
3 Correct 1782 ms 67412 KB Output is correct
4 Correct 1784 ms 67348 KB Output is correct
5 Correct 2103 ms 68112 KB Output is correct
6 Correct 345 ms 64852 KB Output is correct
7 Correct 1814 ms 67344 KB Output is correct
8 Correct 1776 ms 67264 KB Output is correct
9 Correct 2185 ms 68180 KB Output is correct
10 Correct 348 ms 64776 KB Output is correct
11 Correct 1770 ms 67388 KB Output is correct
12 Correct 12 ms 59996 KB Output is correct
13 Execution timed out 8096 ms 411256 KB Time limit exceeded
14 Halted 0 ms 0 KB -