Submission #161005

#	Time	Username	Problem	Language	Result	Execution time	Memory
161005		ArshiaDadras	Factories (JOI14_factories)	C++14	0 / 100	74 ms	44152 KiB

factories

/* In the name of Allah */
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;

const long long INF = 1e18 + 5;
const int N = 5e5 + 5, LG = 18 + 2;
int n, q, h[N], st[N], en[N], par[N][LG];
vector<pair<int, int>> adj[N];
int n1, n2, u1[N], u2[N];
long long dist[N];
struct Segment {
	long long seg[N << 2];
	bool mark[N];

	Segment() {
		memset(seg, 63, sizeof seg);
	}
	void update(int p, long long x, int id = 1, int st = 0, int en = n) {
		if (en - st == 1) {
			seg[id] = x;
			return;
		}
		int mid = st + en >> 1;
		if (p < mid)
			update(p, x, id << 1, st, mid);
		else
			update(p, x, id << 1 | 1, mid, en);
		seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
	}
	long long get(int l, int r, int id = 1, int st = 0, int en = n) {
		if (r <= st || en <= l)
			return INF;
		if (l <= st && en <= r)
			return seg[id];
		int mid = st + en >> 1;
		return min(get(l, r, id << 1, st, mid), get(l, r, id << 1 | 1, mid, en));
	}
	void clear(int id = 1, int st = 0, int en = n) {
		if (seg[id] >= INF)
			return;
		seg[id] = INF;
		if (en - st == 1) {
			mark[st] = false;
			return;
		}
		int mid = st + en >> 1;
		clear(id << 1, st, mid);
		clear(id << 1 | 1, mid, en);
	}
} seg1, seg2;

inline int lca(int u, int v) {
	if (h[u] > h[v])
		swap(u, v);
	for (int i = LG - 1; ~i; i--)
		if (h[v] - h[u] >> i & 1)
			v = par[v][i];
	for (int i = LG - 1; ~i; i--)
		if (par[u][i] ^ par[v][i]) {
			u = par[u][i];
			v = par[v][i];
		}
	return u ^ v? par[u][0]: u;
}

void dfs(int u) {
	static int time = 0;
	for (int i = 0; i < LG - 1; i++)
		par[u][i + 1] = par[par[u][i]][i];
	st[u] = time++;
	for (auto v: adj[u])
		if (v.first ^ par[u][0]) {
			h[v.first] = h[par[v.first][0] = u] + 1;
			dist[v.first] = dist[u] + v.second;
			dfs(v.first);
		}
	en[u] = time;
}

inline bool cmp(int u, int v) {
	return st[u] < st[v];
}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < N - 1; i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	n = N, dfs(0);
}

inline long long solve() {
	long long ans = INF;
	sort(u1, u1 + n1, cmp);
	sort(u2, u2 + n2, cmp);
	seg1.clear(), seg2.clear();
	for (int i = 0; i < n1; i++)
		seg1.update(st[u1[i]], dist[u1[i]]);
	for (int i = 0; i < n2; i++)
		seg2.update(st[u2[i]], dist[u2[i]]);
	for (int i = 0, p = 0; i < n1; i++) {
		ans = min(ans, seg2.get(st[u1[i]], en[u1[i]]) - dist[u1[i]]);
		while (p < n2 && !cmp(u1[i], u2[p]))
			p++;
		if (p < n2) {
			int x = lca(u1[i], u2[p]);
			ans = min(ans, dist[u1[i]] + seg2.get(st[x], en[x]) - 2 * dist[x]);
		}
	}
	for (int i = 0, p = 0; i < n2; i++) {
		ans = min(ans, seg1.get(st[u2[i]], en[u2[i]]) - dist[u2[i]]);
		while (p < n1 && !cmp(u2[i], u1[p]))
			p++;
		if (p < n1) {
			int x = lca(u2[i], u1[p]);
			ans = min(ans, dist[u2[i]] + seg1.get(st[x], en[x]) - 2 * dist[x]);
		}
	}
	return ans;
}

long long Query(int S, int X[], int T, int Y[]) {
	n1 = S, n2 = T;
	copy(X, X + S, u1);
	copy(Y, Y + T, u2);
	return solve();
}

Compilation message (stderr)

factories.cpp: In member function 'void Segment::update(int, long long int, int, int, int)':
factories.cpp:24:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = st + en >> 1;
             ~~~^~~~
factories.cpp: In member function 'long long int Segment::get(int, int, int, int, int)':
factories.cpp:36:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = st + en >> 1;
             ~~~^~~~
factories.cpp: In member function 'void Segment::clear(int, int, int)':
factories.cpp:47:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = st + en >> 1;
             ~~~^~~~
factories.cpp: In function 'int lca(int, int)':
factories.cpp:57:12: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   if (h[v] - h[u] >> i & 1)
       ~~~~~^~~~~~

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