oj.uz

답안 #886244

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

typedef long long ll;

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
#define cln(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define unq(a, n); {vector<int> v; for(int i = 0; i < n; i++) v.pb(a[i]); cln(v); for (int i = 0; i < n; i++) a[i] = lower_bound(all(v), a[i]) - v.begin();}

const ll N = 5e5 + 12, inf = 1e18 + 12;
vector<pii> 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.F != par && !mrk[i.F]) {
			dfs(i.F, u);
			sz[u] += sz[i.F];
		}
}

int find_centroid(int u, int c, int par = -1) {
	for (auto i: g[u])
		if (!mrk[i.F] && i.F != par && sz[i.F] > (c - 1) / 2)
			return find_centroid(i.F, 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.F] && i.F != par)
			fill_cdis(i.F, cent, c + i.S, 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.F])
			decompose(i.F, u);
}

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

ll ask(int u, int v) {
	if (u == -1)
		return inf;
	ll tmp = cdis[u].lower_bound({v, -1})->S;
	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]].pb({b[i], d[i]});
		g[b[i]].pb({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 30 ms 60252 KB Output is correct
2 Correct 1141 ms 71300 KB Output is correct
3 Correct 1747 ms 72036 KB Output is correct
4 Correct 1751 ms 71964 KB Output is correct
5 Correct 2083 ms 77536 KB Output is correct
6 Correct 347 ms 74616 KB Output is correct
7 Correct 1783 ms 76680 KB Output is correct
8 Correct 1772 ms 76720 KB Output is correct
9 Correct 2090 ms 77536 KB Output is correct
10 Correct 343 ms 74308 KB Output is correct
11 Correct 1772 ms 76796 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 60252 KB Output is correct
2 Correct 1141 ms 71300 KB Output is correct
3 Correct 1747 ms 72036 KB Output is correct
4 Correct 1751 ms 71964 KB Output is correct
5 Correct 2083 ms 77536 KB Output is correct
6 Correct 347 ms 74616 KB Output is correct
7 Correct 1783 ms 76680 KB Output is correct
8 Correct 1772 ms 76720 KB Output is correct
9 Correct 2090 ms 77536 KB Output is correct
10 Correct 343 ms 74308 KB Output is correct
11 Correct 1772 ms 76796 KB Output is correct
12 Correct 12 ms 59996 KB Output is correct
13 Execution timed out 8106 ms 411396 KB Time limit exceeded
14 Halted 0 ms 0 KB -