제출 #886256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886256		javotaz	공장들 (JOI14_factories)	C++17	33 / 100	8034 ms	524288 KiB

factories

// 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67