Submission #1292262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292262		blackscreen1	Factories (JOI14_factories)	C++20	100 / 100	3365 ms	422432 KiB

factories

#include "factories.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i < h; i += g)
#define jloop_(m, h, g) for (auto j = m; j < h; j += g)
#define kloop_(m, h, g) for (auto k = m; k < h; k += g)
#define lloop_(m, h, g) for (auto l = m; l < h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll n;
vector<pll> adj[500005];
ll sz[500005], dis[500005], pr[500005];
bool avis[500005];
ll val[500005], pre[500005], cnt, dpt[500005];
pll ord[1000005], sparse[20][1000005];
ll lg[1000005];
void dfs(ll nd, ll pr, ll dp) {
	dpt[nd] = dp;
	ord[cnt] = {dp, nd};
	pre[nd] = cnt;
	cnt++;
	for (auto it : adj[nd]) if (it.second != pr) {dis[it.second] = dis[nd] + it.first; dfs(it.second, nd, dp + 1); ord[cnt] = {dp, nd}; cnt++;}
}
void spar() {
	iloop(0, 2*n) sparse[0][i] = ord[i];
	iloop(1, 20) jloop(0, 2*n - (1<<i)) {
		sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j + (1<<(i-1))]);
	}
}
ll lca(ll x, ll y) {
	x = pre[x], y = pre[y];
	if (x > y) swap(x, y);
	ll i = lg[y-x+1];
	return min(sparse[i][x], sparse[i][y - (1<<i) + 1]).second;
}
ll dfs2(ll nd, ll pr) {
	sz[nd] = 1;
	for (auto it : adj[nd]) if (it.second != pr && !avis[it.second]) sz[nd] += dfs2(it.second, nd);
	return sz[nd];
}
ll dfs3(ll nd, ll pr, ll os) {
	for (auto it : adj[nd]) if (it.second != pr && !avis[it.second] && sz[it.second]*2 > os) return dfs3(it.second, nd, os);
	return nd;
}
void construct(ll prv, ll sn) {
	ll cs = dfs2(sn, -1);
	ll cen = dfs3(sn, -1, cs);
	avis[cen] = 1;
	pr[cen] = prv;
	for (auto it : adj[cen]) if (!avis[it.second]) construct(cen, it.second);
}
void Init(int N, int A[], int B[], int D[]) {
	lg[1] = 0;
	iloop(2, 1000005) lg[i] = lg[i/2] + 1;
	n = N;
	iloop(0, n-1) {
		adj[A[i]].push_back({D[i], B[i]});
		adj[B[i]].push_back({D[i], A[i]});
	}
	dfs(0, -1, 0);
	construct(-1, 0);
	spar();
	iloop(0, n) val[i] = INF;
	/*cout << "sparse:\n";
	iloop(0, 4) {jloop(0, 2*n) {cout << sparse[i][j].first << "," << sparse[i][j].second << " ";} cout << "\n";}
	cout << "lca:\n";
	iloop(0, n) {jloop(0, n) {cout << lca(i, j) << " ";} cout << "\n";}*/
	//iloop(0, n) cout << pr[i] << " ";
	//cout << "h\n";
}
long long Query(int S, int X[], int T, int Y[]) {
	iloop(0, S) {
		ll nd = X[i];
		while (nd != -1) {
			val[nd] = min(val[nd], dis[nd] + dis[X[i]] - 2*dis[lca(nd, X[i])]);
			nd = pr[nd];
		}
	}
	//iloop(0, n) cout << val[i] << ",";
	//cout << "h\n";
	
	ll cans = INF;
	iloop(0, T) {
		ll nd = Y[i];
		while (nd != -1) {cans = min(cans, dis[Y[i]] + dis[nd] - 2*dis[lca(nd, Y[i])] + val[nd]); nd = pr[nd];}
	}
	iloop(0, S) while (val[X[i]] != INF) {val[X[i]] = INF; X[i] = pr[X[i]];}
	return cans;
}

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