oj.uz

Submission #363686

# Submission time Handle Problem Language Result Execution time Memory
363686 2021-02-06T20:45:06 Z shivensinha4 Factories (JOI14_factories) C++17
100 / 100
 7176 ms 345984 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
#ifndef mlocal
#include "factories.h"
#endif

class SparseTable {
	vector<vector<array<int, 2>>> st;
	int n;
	
	void buildTable(vector<array<int, 2>> &raw) {
		int k = __lg(n)+1;
		st.resize(n, vector<array<int, 2>> (k));
		for_(i, 0, n) st[i][0] = raw[i];
		for_(p, 1, k+1) for_(i, 0, n - (1<<p) + 1)
				st[i][p] = min(st[i][p-1], st[i + (1 << (p-1))][p-1]);
	}

public:
	void build(vector<array<int, 2>> &nums) {
		n = nums.size();
		buildTable(nums);
	}
	
	int mn(int l, int r) {
		int p = __lg(r-l+1);
		return min(st[l][p], st[r - (1<<p) + 1][p])[1];
	}
};


int n;
vector<vector<array<ll, 2>>> adjList;
vi removed, subtreeSize, centroid, tin, depth;
vector<ll> rootDist, whiteDist;
vector<array<int, 2>> tour;
SparseTable st;
const ll INF = 1e15;

int dfs(int p, int parent) {
	int s = 1;
	tin[p] = tour.size();
	tour.push_back({depth[p], p});
	
	for (auto i: adjList[p]) if (i[0] != parent) {
			rootDist[i[0]] = rootDist[p]+i[1];
			depth[i[0]] = depth[p]+1;
			s += dfs(i[0], p);
			tour.push_back({depth[p], p});
		}
	
	subtreeSize[p] = s;
	return s;
}

int lca(int u, int v) {
	return st.mn(min(tin[u], tin[v]), max(tin[u], tin[v]));
}

ll dist(int u, int v) {
	int lc = lca(u, v);
	return rootDist[u] + rootDist[v] - 2*rootDist[lc];
}

void decompose(int p, int c) {
	int invalidChild = -1, sizeLimit = (subtreeSize[p] >> 1);
	for (auto i: adjList[p]) if (!removed[i[0]] and subtreeSize[i[0]] > sizeLimit) {
			invalidChild = i[0];
			break;
		}
	
	if (invalidChild != -1) {
		subtreeSize[p] -= subtreeSize[invalidChild];
		subtreeSize[invalidChild] += subtreeSize[p];
		return decompose(invalidChild, c);
	}
	
	removed[p] = true;
	centroid[p] = c;
	for (auto i: adjList[p]) if (!removed[i[0]]) {
			centroid[i[0]] = p;
			decompose(i[0], p);
		}
}

vi updated;
int pt = 0;

void update(int p) {
	int v = p;
	while (v != -1) {
		ll d = dist(p, v);
		whiteDist[v] = min(whiteDist[v], d);
		updated[pt++] = v;
		v = centroid[v];
	}
}

ll ans(int p) {
	ll val = INF;
	int v = p;
	while (v != -1) {
		val = min(val, whiteDist[v] + dist(p, v));
		v = centroid[v];
	}
	return (val == 1e9 ? -1 : val);
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	adjList.resize(n); subtreeSize.resize(n); removed.resize(n); centroid.resize(n, -1); depth.resize(n); tin.resize(n); rootDist.resize(n); whiteDist.resize(n, INF); updated.resize(10*n);
	for_(i, 0, n-1) {
		int a = A[i], b = B[i]; ll w = D[i];
		adjList[a].push_back({b, w});
		adjList[b].push_back({a, w});
	}
	
	dfs(0, 0);
	decompose(0, -1);
	st.build(tour);
}

ll Query(int S, int X[], int T, int Y[]) {
	pt = 0;
	
	for_(i, 0, S) update(X[i]);
	ll val = INF;
	for_(i, 0, T) val = min(val, ans(Y[i]));
	for_(i, 0, pt) whiteDist[updated[i]] = INF;
	
	return val;
}

#ifdef mlocal
int main() {
	freopen("test.in", "r", stdin);

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, q;
	cin >> N >> q;
	int A[100], B[100], D[100];
	for_(i, 0, N - 1) {
		int a, b, w;
		cin >> a >> b >> w;
		A[i] = a;
		B[i] = b;
		D[i] = w;
	}

	Init(N, A, B, D);

	int X[100], Y[100];
	while (q--) {
		int S, T;
		cin >> S >> T;
		for_(i, 0, S) cin >> X[i];
		for_(i, 0, T) cin >> Y[i];
		cout << Query(S, X, T, Y) << endl;
	}

	return 0;
}
#endif

Compilation message

factories.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
factories.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1004 KB Output is correct
2 Correct 630 ms 11344 KB Output is correct
3 Correct 870 ms 11276 KB Output is correct
4 Correct 817 ms 11464 KB Output is correct
5 Correct 833 ms 11884 KB Output is correct
6 Correct 353 ms 11244 KB Output is correct
7 Correct 825 ms 11372 KB Output is correct
8 Correct 820 ms 11244 KB Output is correct
9 Correct 820 ms 11756 KB Output is correct
10 Correct 350 ms 11116 KB Output is correct
11 Correct 822 ms 11376 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3513 ms 291904 KB Output is correct
3 Correct 3882 ms 298132 KB Output is correct
4 Correct 1686 ms 289472 KB Output is correct
5 Correct 4825 ms 345984 KB Output is correct
6 Correct 4040 ms 298944 KB Output is correct
7 Correct 3159 ms 64944 KB Output is correct
8 Correct 1004 ms 63964 KB Output is correct
9 Correct 3318 ms 71424 KB Output is correct
10 Correct 3323 ms 66060 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1004 KB Output is correct
2 Correct 630 ms 11344 KB Output is correct
3 Correct 870 ms 11276 KB Output is correct
4 Correct 817 ms 11464 KB Output is correct
5 Correct 833 ms 11884 KB Output is correct
6 Correct 353 ms 11244 KB Output is correct
7 Correct 825 ms 11372 KB Output is correct
8 Correct 820 ms 11244 KB Output is correct
9 Correct 820 ms 11756 KB Output is correct
10 Correct 350 ms 11116 KB Output is correct
11 Correct 822 ms 11376 KB Output is correct
12 Correct 3 ms 620 KB Output is correct
13 Correct 3513 ms 291904 KB Output is correct
14 Correct 3882 ms 298132 KB Output is correct
15 Correct 1686 ms 289472 KB Output is correct
16 Correct 4825 ms 345984 KB Output is correct
17 Correct 4040 ms 298944 KB Output is correct
18 Correct 3159 ms 64944 KB Output is correct
19 Correct 1004 ms 63964 KB Output is correct
20 Correct 3318 ms 71424 KB Output is correct
21 Correct 3323 ms 66060 KB Output is correct
22 Correct 4981 ms 293000 KB Output is correct
23 Correct 5103 ms 295340 KB Output is correct
24 Correct 6069 ms 298916 KB Output is correct
25 Correct 6066 ms 303124 KB Output is correct
26 Correct 6058 ms 299568 KB Output is correct
27 Correct 7176 ms 338424 KB Output is correct
28 Correct 2097 ms 293052 KB Output is correct
29 Correct 6052 ms 298956 KB Output is correct
30 Correct 6157 ms 297796 KB Output is correct
31 Correct 6032 ms 299108 KB Output is correct
32 Correct 3386 ms 72820 KB Output is correct
33 Correct 1008 ms 64348 KB Output is correct
34 Correct 2656 ms 61972 KB Output is correct
35 Correct 2608 ms 62188 KB Output is correct
36 Correct 3178 ms 63456 KB Output is correct
37 Correct 3183 ms 63452 KB Output is correct