oj.uz

답안 #886256

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

#pragma  GCC optimize ("O2,unroll-loops")
#pragma  GCC optimize ("Ofast")
#pragma  gcc optimize("Ofast")
#pragma  optimize(Ofast)
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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];
unordered_map<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][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][v]);
	add(cpar[u], v);
}

ll ask(int u, int v) {
	if (u == -1)
		return inf;
	ll tmp = cdis[u][v];
	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;
}

Compilation message

factories.cpp:8: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    8 | #pragma  gcc optimize("Ofast")
      | 
factories.cpp:9: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    9 | #pragma  optimize(Ofast)
      |

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 62040 KB Output is correct
2 Correct 426 ms 68116 KB Output is correct
3 Correct 557 ms 68688 KB Output is correct
4 Correct 545 ms 68688 KB Output is correct
5 Correct 625 ms 69460 KB Output is correct
6 Correct 192 ms 67104 KB Output is correct
7 Correct 537 ms 68632 KB Output is correct
8 Correct 570 ms 68688 KB Output is correct
9 Correct 638 ms 69360 KB Output is correct
10 Correct 187 ms 67188 KB Output is correct
11 Correct 554 ms 68732 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 62168 KB Output is correct
2 Correct 3715 ms 352368 KB Output is correct
3 Correct 5036 ms 483420 KB Output is correct
4 Correct 789 ms 200660 KB Output is correct
5 Correct 6234 ms 524288 KB Output is correct
6 Correct 5299 ms 484036 KB Output is correct
7 Correct 3640 ms 152872 KB Output is correct
8 Correct 469 ms 103708 KB Output is correct
9 Correct 4224 ms 161116 KB Output is correct
10 Correct 3606 ms 153284 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 62040 KB Output is correct
2 Correct 426 ms 68116 KB Output is correct
3 Correct 557 ms 68688 KB Output is correct
4 Correct 545 ms 68688 KB Output is correct
5 Correct 625 ms 69460 KB Output is correct
6 Correct 192 ms 67104 KB Output is correct
7 Correct 537 ms 68632 KB Output is correct
8 Correct 570 ms 68688 KB Output is correct
9 Correct 638 ms 69360 KB Output is correct
10 Correct 187 ms 67188 KB Output is correct
11 Correct 554 ms 68732 KB Output is correct
12 Correct 13 ms 62168 KB Output is correct
13 Correct 3715 ms 352368 KB Output is correct
14 Correct 5036 ms 483420 KB Output is correct
15 Correct 789 ms 200660 KB Output is correct
16 Correct 6234 ms 524288 KB Output is correct
17 Correct 5299 ms 484036 KB Output is correct
18 Correct 3640 ms 152872 KB Output is correct
19 Correct 469 ms 103708 KB Output is correct
20 Correct 4224 ms 161116 KB Output is correct
21 Correct 3606 ms 153284 KB Output is correct
22 Correct 4757 ms 371388 KB Output is correct
23 Correct 4908 ms 382052 KB Output is correct
24 Correct 7544 ms 488588 KB Output is correct
25 Correct 7634 ms 490516 KB Output is correct
26 Correct 7604 ms 489224 KB Output is correct
27 Execution timed out 8034 ms 524288 KB Time limit exceeded
28 Halted 0 ms 0 KB -