oj.uz

Submission #273499

# Submission time Handle Problem Language Result Execution time Memory
273499 2020-08-19T05:37:40 Z shivensinha4 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 336272 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include "factories.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'
 
class SparseTable {
	vector<vector<ii>> st;
	vector<ll> log; vector<ii> raw;
	int n;
 
	void computeLog() {
		log.resize(n+1, -1);
		int p = 0, two_pow = 1;
		while (two_pow <= n) {
			log[two_pow] = p++;
			two_pow *= 2;
		}
		int prev = 0;
		for_(i, 1, n+1) {
			if (log[i] != -1) prev = log[i];
			else log[i] = prev;
		}
	}
 
	void buildTable() {
		int k = log[n]+1;
		st.resize(n, vector<ii> (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<ii> nums) {
		raw = nums;
		n = nums.size();
		computeLog();
		buildTable();
	}
 
	int mn(int l, int r) {
		int p = log[r-l+1];
		return min(st[l][p], st[r - (1<<p) + 1][p]).second;
	}
};
 
 
int n;
vector<vector<pair<int, ll>>> adjList;
vi removed, subtreeSize, centroid, tin, depth;
vector<ll> rootDist, whiteDist;
vector<ii> tour;
SparseTable st;
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.first != parent) {
		rootDist[i.first] = rootDist[p]+i.second;
		depth[i.first] = depth[p]+1;
		s += dfs(i.first, 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.first] and subtreeSize[i.first] > sizeLimit) {
		invalidChild = i.first;
		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.first]) {
		centroid[i.first] = p;
		decompose(i.first, p);
	}
}

set<int> updated;

void update(int p) {
	int v = p;
	while (v != -1) {
		ll d = dist(p, v);
		whiteDist[v] = min(whiteDist[v], d);
		updated.insert(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);
	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[]) {
	updated.clear();
	
	for_(i, 0, S) update(X[i]);
	ll val = INF;
	for_(i, 0, T) val = min(val, ans(Y[i]));
	for (int i: updated) whiteDist[i] = INF;
	
	return val;
}
 
//int main() {
	//#ifndef ONLINE_JUDGE
	//freopen("test.in", "r", stdin);
	//#endif
	
	//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;
//}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1024 KB Output is correct
2 Correct 1450 ms 12284 KB Output is correct
3 Correct 2262 ms 12396 KB Output is correct
4 Correct 2500 ms 13536 KB Output is correct
5 Correct 2583 ms 14200 KB Output is correct
6 Correct 746 ms 13672 KB Output is correct
7 Correct 2563 ms 14484 KB Output is correct
8 Correct 2327 ms 14760 KB Output is correct
9 Correct 2157 ms 15044 KB Output is correct
10 Correct 599 ms 14588 KB Output is correct
11 Correct 1881 ms 14776 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5806 ms 295576 KB Output is correct
3 Correct 6717 ms 303340 KB Output is correct
4 Correct 2128 ms 294852 KB Output is correct
5 Correct 7707 ms 336272 KB Output is correct
6 Correct 7041 ms 301264 KB Output is correct
7 Correct 7127 ms 65360 KB Output is correct
8 Correct 1476 ms 64240 KB Output is correct
9 Correct 6905 ms 70080 KB Output is correct
10 Correct 6732 ms 66032 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1024 KB Output is correct
2 Correct 1450 ms 12284 KB Output is correct
3 Correct 2262 ms 12396 KB Output is correct
4 Correct 2500 ms 13536 KB Output is correct
5 Correct 2583 ms 14200 KB Output is correct
6 Correct 746 ms 13672 KB Output is correct
7 Correct 2563 ms 14484 KB Output is correct
8 Correct 2327 ms 14760 KB Output is correct
9 Correct 2157 ms 15044 KB Output is correct
10 Correct 599 ms 14588 KB Output is correct
11 Correct 1881 ms 14776 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 5806 ms 295576 KB Output is correct
14 Correct 6717 ms 303340 KB Output is correct
15 Correct 2128 ms 294852 KB Output is correct
16 Correct 7707 ms 336272 KB Output is correct
17 Correct 7041 ms 301264 KB Output is correct
18 Correct 7127 ms 65360 KB Output is correct
19 Correct 1476 ms 64240 KB Output is correct
20 Correct 6905 ms 70080 KB Output is correct
21 Correct 6732 ms 66032 KB Output is correct
22 Execution timed out 8067 ms 298452 KB Time limit exceeded
23 Halted 0 ms 0 KB -