제출 #549997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
549997		David1425	공장들 (JOI14_factories)	C++17	100 / 100	4962 ms	214760 KiB

factories

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("O3")

using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define ppb pop_back
#define all(x) (x).begin(),(x).end()
#define sz(x) int((x).size())
#define MEM(x, v) memset(x, v, sizeof(x))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
template<typename T> using reverse_pq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename CMP> using ordered_set = tree<T, null_type, CMP, rb_tree_tag, tree_order_statistics_node_update>;

void si() {}
template<typename T, typename... U>
void si(T& x, U&... u) {char _;int neg=1;do{while((x=getchar())<'0'&&(x!='-')){};if(x=='-'){neg=-1;x=getchar();}for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0);x*=neg;si(u...);}

template<typename T, typename U> typename common_type<T, U>::type min(T a, U b) { return (((a) < (b)) ? (a) : (b)); }
template<typename T, typename U> typename common_type<T, U>::type max(T a, U b) { return (((a) > (b)) ? (a) : (b)); }
template<typename T, typename U> typename common_type<T, U>::type minv(T a, U b) { return min(a, b); }
template<typename T, typename... U> typename common_type<T, U...>::type minv(T a, U... b) { return min(a, minv(b...)); }
template<typename T, typename U> typename common_type<T, U>::type maxv(T a, U b) { return max(a, b); }
template<typename T, typename... U> typename common_type<T, U...>::type maxv(T a, U... b) { return max(a, maxv(b...)); }

int lg2(long long x) { return 63 - __builtin_clzll(x); }
int lg2(int x) { return 31 - __builtin_clz(x); }

mt19937 rng(uint64_t(new char)+chrono::steady_clock::now().time_since_epoch().count());

const ll MOD = 1e9+7;
const ll HASH = 131;
const int MM = 5e5+5;

int n;
vector<pii> adj[MM];

vi s(MM);
vector<bool> vis(MM);
void dfs1(int u, int p) {
	s[u] = 1;
	for (auto [v,w] : adj[u]) {
		if (v != p && !vis[v]) {
			dfs1(v,u);
			s[u] += s[v];
		}
	}
}

int centroid(int u, int p, int x) {
	for (auto [v,w] : adj[u]) {
		if (!vis[v] && v != p && s[v]*2 > x) return centroid(v,u,x);
	}
	return u;
}

vl dep[MM];
void dfs2(int u, int p, ll d) {
	dep[u].pb(d);
	for (auto [v,w] : adj[u]) {
		if (v != p && !vis[v]) {
			dfs2(v, u, d+w);
		}
	}
}

vi par(MM,-1);
void search(int u, int p) {
	dfs1(u,p);
	u = centroid(u,-1,s[u]);
	par[u] = p;
	vis[u] = 1;
	dfs2(u,p,0);
	
	for (auto [v,w] : adj[u]) {
		if (!vis[v]) {
			search(v,u);
		}
	}
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < N-1; i++) {
		adj[A[i]].pb({B[i],D[i]});
		adj[B[i]].pb({A[i],D[i]});
		// cout << A[i] << " " << B[i] << " " << D[i] << "\n";
	}
	search(0,-1);
	for (int i = 0; i < n; i++) reverse(all(dep[i]));
	// fill(vis.begin(), vis.begin()+N,0);
	// fill(all(vis),0);
}

vl res(MM, LINF);
ll Query(int s, int x[], int t, int y[]) {
	ll ans = LINF;
	for (int i = 0; i < s; i++) {
		for (int j = x[i], pos = 0; j != -1; j = par[j], pos++) {
			res[j] = min(res[j], dep[x[i]][pos]);
		}
	}
	for (int i = 0; i < t; i++) {
		for (int j = y[i], pos = 0; j != -1; j = par[j], pos++) {
			ans = min(ans, res[j]+dep[y[i]][pos]);
		}
	}
	for (int i = 0; i < s; i++) for (int j = x[i]; j != -1; j = par[j]) res[j] = LINF;
	return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67