Submission #99021

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
99021	2019-02-28T05:43:27 Z	qkxwsm	Factories (JOI14_factories)	C++14	100 / 100	6505 ms	240516 KB

factories

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
#include "factories.h"

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

random_device(rd);
mt19937 rng(rd());
const long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

struct custom_hash
{
	template<class T>
	unsigned long long operator()(T v) const
	{
		unsigned long long x = v;
		x += FIXED_RANDOM;
		// x += 11400714819323198485ull;
		// x = (x ^ (x >> 30)) * 13787848793156543929ull;
		x = (x ^ (x >> 27)) * 10723151780598845931ull;
		return x ^ (x >> 31);
	}
};

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U> using hash_table = gp_hash_table<T, U, custom_hash>;

template<class T>
T randomize(T mod)
{
	return (uniform_int_distribution<T>(0, mod - 1))(rng);
}
template<class T>
void readi(T &x)
{
	x = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		x = -x;
	}
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int buf[20], n = 0;
	while(output)
	{
		buf[n] = ((output % 10));
		output /= 10;
		n++;
	}
	for (n--; n >= 0; n--)
	{
		putchar(buf[n] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long expo(long long a, long long e, long long mod)
{
	return ((e == 0) ? 1 : ((expo(a * a % mod, e >> 1, mod)) * ((e & 1) ? a : 1) % mod));
}
template<class T, class U>
void nmod(T &x, U mod)
{
	if (x >= mod) x -= mod;
}
template<class T>
T gcd(T a, T b)
{
	return (b ? gcd(b, a % b) : a);
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define DBG(x) cerr << #x << " = " << (x) << endl
#define SZ(x) ((int) ((x).size()))
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-9;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 500013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<pdd> vpd;

int N, M, T;
vpl edge[MAXN], edge1[MAXN];
int parent[MAXN], depth[MAXN];
int parent1[MAXN];
int mintable[25][2 * MAXN];
int ord[2 * MAXN], rord[2 * MAXN];
int st[MAXN], ft[MAXN];
ll dis[MAXN];
ll dp[2][MAXN];
int ed[MAXN];
vi L, R, V, pts;
ll ans;

int comb1(int a, int b)
{
	return (depth[ord[a]] < depth[ord[b]] ? a : b);
}
int lca(int u, int v)
{
	u = rord[u]; v = rord[v];
	if (u > v) swap(u, v);
	int sz = 31 - __builtin_clz(v - u + 1);
	int res = ord[comb1(mintable[sz][u], mintable[sz][v - (1 << sz) + 1])];
	return res;
}
void dfs(int u)
{
	ord[M] = u;
	rord[u] = M;
	M++;
	st[u] = T;
	ft[u] = T;
	T++;
	for (pii p : edge[u])
	{
		int v = p.se;
		if (v == parent[u]) continue;
		parent[v] = u;
		depth[v] = depth[u] + 1;
		dis[v] = dis[u] + p.fi;
		dfs(v);
		ft[u] = ft[v];
		ord[M] = u;
		M++;
	}
}
ll dist(int u, int v)
{
	// cerr << u << ' ' << v << ' ' << lca(u, v) << endl;
	return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}
void Init(int n, int A[], int B[], int D[])
{
	N = n;
	FOR(i, 0, N - 1)
	{
		int u = A[i], v = B[i], d = D[i];
		edge[u].PB({d, v});
		edge[v].PB({d, u});
	}
	parent[0] = N;
	dfs(0);
	FOR(i, 0, M)
	{
		mintable[0][i] = i;
	}
	FOR(j, 1, 21)
	{
		FOR(i, 0, M)
		{
			mintable[j][i] = mintable[j - 1][i];
			if (i + (1 << (j - 1)) < M)
			{
				mintable[j][i] = comb1(mintable[j][i], mintable[j - 1][i + (1 << (j - 1))]);
			}
		}
	}
	FOR(i, 0, N)
	{
		dp[0][i] = dp[1][i] = LLINF;
		parent1[i] = N;
		ed[i] = -1;
	}
}
bool cmp(int a, int b)
{
	return st[a] < st[b];
}
int ok(int idx)
{
	int u = V[idx];
	int e;
	// cerr << "hi " << u << ' ' << parent1[u] << endl;
	for (e = idx + 1; e < SZ(V) && st[u] <= st[V[e]] && st[V[e]] <= ft[u]; )
	{
		int v = V[e];
		ll d = dis[v] - dis[u];
		edge1[u].PB({d, v});
		edge1[v].PB({d, u});
		parent1[v] = u;
		// cerr << " parent1 " << v << " = " << u << endl;
		e = ok(e);
	}
	return e;
}
void go(int u)
{
	for (pll p : edge1[u])
	{
		int v = p.se; ll d = p.fi;
		if (v == parent1[u]) continue;
		// cerr << u << " -> " << v << ' ' << parent1[u] << endl;
		go(v);
		ckmin(dp[0][u], dp[0][v] + d);
		ckmin(dp[1][u], dp[1][v] + d);
	}
	if (ed[u] == 0) dp[0][u] = 0;
	if (ed[u] == 1) dp[1][u] = 0;
}
void go1(int u)
{
	for (pll p : edge1[u])
	{
		int v = p.se; ll d = p.fi;
		if (v == parent1[u]) continue;
		ckmin(dp[0][v], dp[0][u] + d);
		ckmin(dp[1][v], dp[1][u] + d);
		go1(v);
	}
}


long long Query(int S, int X[], int T, int Y[])
{
	FOR(i, 0, S) L.PB(X[i]);
	FOR(i, 0, T) R.PB(Y[i]);
	for (int u : L)
	{
		pts.PB(u);
		ed[u] = 0;
	}
	for (int u : R)
	{
		pts.PB(u);
		ed[u] = 1;
	}
	sort(ALL(pts), cmp);
	FOR(i, 0, SZ(pts))
	{
		V.PB(pts[i]);
		if (i)
		{
			int x = lca(pts[i - 1], pts[i]);
			V.PB(x);
		}
	}
	sort(ALL(V), cmp);
	V.erase(unique(ALL(V)), V.end());
	ok(0);
	go(V[0]);
	go1(V[0]);
	// priority_queue<pll, vector<pll>, greater<pll> > pq;
	// for (int u : L)
	// {
	// 	dp[0][u] = 0;
	// 	pq.push({0, u});
	// }
	// while(!pq.empty())
	// {
	// 	ll d = pq.top().fi, u = pq.top().se;
	// 	pq.pop();
	// 	if (d != dp[0][u]) continue;
	// 	for (pll p : edge1[u])
	// 	{
	// 		int u = p.se; ll nd = d + p.fi;
	// 		if (nd < dp[0][u])
	// 		{
	// 			dp[0][u] = nd;
	// 			pq.push({nd, u});
	// 		}
	// 	}
	// }
	// for (int u : R)
	// {
	// 	dp[1][u] = 0;
	// 	pq.push({0, u});
	// }
	// while(!pq.empty())
	// {
	// 	ll d = pq.top().fi, u = pq.top().se;
	// 	pq.pop();
	// 	if (d != dp[1][u]) continue;
	// 	for (pll p : edge1[u])
	// 	{
	// 		int u = p.se; ll nd = d + p.fi;
	// 		if (nd < dp[1][u])
	// 		{
	// 			dp[1][u] = nd;
	// 			pq.push({nd, u});
	// 		}
	// 	}
	// }
	ans = LLINF;
	for (int u : V)
	{
		ckmin(ans, dp[0][u] + dp[1][u]);
	}
	for (int u : V)
	{
		dp[0][u] = LLINF;
		dp[1][u] = LLINF;
		ed[u] = -1;
		edge1[u].clear();
		parent1[u] = N;
	}
	L.clear();
	R.clear();
	pts.clear();
	V.clear();
	//u need to build the tree!
	return ans;
}

/* READ READ READ
* int overflow, maxn too small, special cases (n=1?, two distinct?), cin.tie() interactive
* reread the problem, try small cases
* note down possible sources of error as you go
* do smth instead of nothing
*/

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	24576 KB	Output is correct
2	Correct	1208 ms	35456 KB	Output is correct
3	Correct	1088 ms	35192 KB	Output is correct
4	Correct	1253 ms	35312 KB	Output is correct
5	Correct	773 ms	35448 KB	Output is correct
6	Correct	695 ms	35112 KB	Output is correct
7	Correct	1044 ms	35112 KB	Output is correct
8	Correct	1026 ms	35356 KB	Output is correct
9	Correct	829 ms	35448 KB	Output is correct
10	Correct	743 ms	35064 KB	Output is correct
11	Correct	1098 ms	35068 KB	Output is correct

Subtask #2

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	24316 KB	Output is correct
2	Correct	2573 ms	188672 KB	Output is correct
3	Correct	2832 ms	190588 KB	Output is correct
4	Correct	2100 ms	186304 KB	Output is correct
5	Correct	2645 ms	210728 KB	Output is correct
6	Correct	2936 ms	192408 KB	Output is correct
7	Correct	2511 ms	66808 KB	Output is correct
8	Correct	1935 ms	66380 KB	Output is correct
9	Correct	2201 ms	70844 KB	Output is correct
10	Correct	2653 ms	67928 KB	Output is correct

Subtask #3

67.0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	24576 KB	Output is correct
2	Correct	1208 ms	35456 KB	Output is correct
3	Correct	1088 ms	35192 KB	Output is correct
4	Correct	1253 ms	35312 KB	Output is correct
5	Correct	773 ms	35448 KB	Output is correct
6	Correct	695 ms	35112 KB	Output is correct
7	Correct	1044 ms	35112 KB	Output is correct
8	Correct	1026 ms	35356 KB	Output is correct
9	Correct	829 ms	35448 KB	Output is correct
10	Correct	743 ms	35064 KB	Output is correct
11	Correct	1098 ms	35068 KB	Output is correct
12	Correct	28 ms	24316 KB	Output is correct
13	Correct	2573 ms	188672 KB	Output is correct
14	Correct	2832 ms	190588 KB	Output is correct
15	Correct	2100 ms	186304 KB	Output is correct
16	Correct	2645 ms	210728 KB	Output is correct
17	Correct	2936 ms	192408 KB	Output is correct
18	Correct	2511 ms	66808 KB	Output is correct
19	Correct	1935 ms	66380 KB	Output is correct
20	Correct	2201 ms	70844 KB	Output is correct
21	Correct	2653 ms	67928 KB	Output is correct
22	Correct	6185 ms	199328 KB	Output is correct
23	Correct	5048 ms	225096 KB	Output is correct
24	Correct	6505 ms	226512 KB	Output is correct
25	Correct	6065 ms	229716 KB	Output is correct
26	Correct	5921 ms	220048 KB	Output is correct
27	Correct	5008 ms	240516 KB	Output is correct
28	Correct	3691 ms	218928 KB	Output is correct
29	Correct	5545 ms	219128 KB	Output is correct
30	Correct	5927 ms	218708 KB	Output is correct
31	Correct	5827 ms	219064 KB	Output is correct
32	Correct	2636 ms	89516 KB	Output is correct
33	Correct	1981 ms	84480 KB	Output is correct
34	Correct	2517 ms	79188 KB	Output is correct
35	Correct	2928 ms	79096 KB	Output is correct
36	Correct	2916 ms	79588 KB	Output is correct
37	Correct	2998 ms	79524 KB	Output is correct