oj.uz

Submission #821784

# Submission time Handle Problem Language Result Execution time Memory
821784 2023-08-11T16:25:47 Z OAleksa Factories (JOI14_factories) C++14
100 / 100
 5005 ms 131444 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define f first
#define s second
using namespace std; 
const int maxn = 5e5 + 69;
const int lg = 20;
int up[maxn][lg];
int timer, tin[maxn], tout[maxn], sz[maxn], par[maxn], vis[maxn];
vector<pair<int, int>> g[maxn];
const long long inf = 1e18;
vector<long long> d(maxn, inf), dis(maxn);
void find_sz(int v, int p) {
	if(vis[v]) {
		sz[v] = 0;
		return;
	}
	sz[v] = 1;
	for(auto u : g[v]) {
		if(u.f != p) {
			find_sz(u.f, v);
			sz[v] += sz[u.f];
		}
	}
}

int find_cen(int v, int p, int n) {
	for(auto u : g[v]) {
		if(u.f != p && !vis[u.f] && sz[u.f] > n / 2)
			return find_cen(u.f, v, n);
	}
	return v;
}

void dfs(int v, int p) {
	find_sz(v, -1);
	int c = find_cen(v, -1, sz[v]);
	par[c] = p;
	vis[c] = 1;
	for(auto u : g[c]) {
		if(!vis[u.f])
			dfs(u.f, c);
	}
}

bool is_anc(int v,int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int lca(int a, int b) {
	if(is_anc(a, b))
		return a;
	else if(is_anc(b, a))
		return b;
	for(int i = lg - 1;i >= 0;i--) {
		if(!is_anc(up[a][i], b) && up[a][i] != -1)
			a = up[a][i];
	}
	return up[a][0];
}

long long dist(int a, int b) {
	int lc = lca(a, b);
	return dis[a] + dis[b] - 2ll * dis[lc];
}

void dfs1(int v,int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	for(int i = 1;i < lg;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for(auto u : g[v]) {
		if(u.f != p) {
			dis[u.f] = dis[v] + u.s;
			dfs1(u.f, v);
		}
	}
	tout[v] = timer;
}

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


long long Query(int S, int X[], int T, int Y[]) {
 	for(int i = 0;i < S;i++)
  		d[X[i]] = 0;
  	long long ans = inf;
	for(int i = 0;i < S;i++) {
		int t = X[i], y = X[i];
		while(y != -1) {
			d[y] = min(d[y], dist(t, y));
			y = par[y];
		}
	}
	for(int i = 0;i < T;i++) {
		int t = Y[i], c = Y[i];
		while(c != -1) {
			ans = min(ans, dist(c, t) + d[c]);
			c = par[c];
		}
	}
	for(int i = 0;i < S;i++) {
		int y = X[i];
		while(y != -1) {
			d[y] = inf;
			y = par[y];
		}
	}
	return ans;
}



// signed main()
// {
	// ios_base::sync_with_stdio(false);
	// cin.tie(0);
	// cout.tie(0);
	// int tt = 1;
	// //cin >> tt;
	// while(tt--) {
		// int n, q;
		// cin >> n >> q;
		// int a[n - 1], b[n - 1], c[n - 1];
		// for(int i = 0;i < n - 1;i++)
			// cin >> a[i] >> b[i] >> c[i];
		// Init(n, a, b, c);
		// for(int i = 0;i < q;i++) {
			// int s, t;
			// cin >> s >> t;
			// int x[s];
			// for(int j = 0;j < s;j++)
				// cin >> x[j];
			// int y[t];
			// for(int j = 0;j < t;j++)
				// cin >> y[j];
			// cout << Query(s, x, t, y) << "\n";
		// }
	// }
   // return 0;
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20264 KB Output is correct
2 Correct 311 ms 28584 KB Output is correct
3 Correct 586 ms 28600 KB Output is correct
4 Correct 558 ms 28628 KB Output is correct
5 Correct 397 ms 28904 KB Output is correct
6 Correct 158 ms 28620 KB Output is correct
7 Correct 565 ms 28608 KB Output is correct
8 Correct 557 ms 28652 KB Output is correct
9 Correct 409 ms 28896 KB Output is correct
10 Correct 164 ms 28728 KB Output is correct
11 Correct 539 ms 28636 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20084 KB Output is correct
2 Correct 1403 ms 100192 KB Output is correct
3 Correct 2955 ms 102828 KB Output is correct
4 Correct 517 ms 101300 KB Output is correct
5 Correct 2604 ms 131444 KB Output is correct
6 Correct 3199 ms 104396 KB Output is correct
7 Correct 1561 ms 46076 KB Output is correct
8 Correct 247 ms 46544 KB Output is correct
9 Correct 1037 ms 50168 KB Output is correct
10 Correct 1616 ms 47228 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20264 KB Output is correct
2 Correct 311 ms 28584 KB Output is correct
3 Correct 586 ms 28600 KB Output is correct
4 Correct 558 ms 28628 KB Output is correct
5 Correct 397 ms 28904 KB Output is correct
6 Correct 158 ms 28620 KB Output is correct
7 Correct 565 ms 28608 KB Output is correct
8 Correct 557 ms 28652 KB Output is correct
9 Correct 409 ms 28896 KB Output is correct
10 Correct 164 ms 28728 KB Output is correct
11 Correct 539 ms 28636 KB Output is correct
12 Correct 9 ms 20084 KB Output is correct
13 Correct 1403 ms 100192 KB Output is correct
14 Correct 2955 ms 102828 KB Output is correct
15 Correct 517 ms 101300 KB Output is correct
16 Correct 2604 ms 131444 KB Output is correct
17 Correct 3199 ms 104396 KB Output is correct
18 Correct 1561 ms 46076 KB Output is correct
19 Correct 247 ms 46544 KB Output is correct
20 Correct 1037 ms 50168 KB Output is correct
21 Correct 1616 ms 47228 KB Output is correct
22 Correct 2056 ms 102120 KB Output is correct
23 Correct 2058 ms 104684 KB Output is correct
24 Correct 4981 ms 104696 KB Output is correct
25 Correct 4781 ms 108304 KB Output is correct
26 Correct 5005 ms 105068 KB Output is correct
27 Correct 3573 ms 128168 KB Output is correct
28 Correct 611 ms 105292 KB Output is correct
29 Correct 4773 ms 104584 KB Output is correct
30 Correct 4750 ms 103996 KB Output is correct
31 Correct 4957 ms 104632 KB Output is correct
32 Correct 1065 ms 51372 KB Output is correct
33 Correct 245 ms 46948 KB Output is correct
34 Correct 684 ms 44156 KB Output is correct
35 Correct 799 ms 44048 KB Output is correct
36 Correct 1824 ms 44720 KB Output is correct
37 Correct 1817 ms 44936 KB Output is correct