oj.uz

Submission #821782

# Submission time Handle Problem Language Result Execution time Memory
821782 2023-08-11T16:23:41 Z OAleksa Factories (JOI14_factories) C++14
15 / 100
 553 ms 87972 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define f first
#define s second
using namespace std; 
const int maxn = 1e5 + 69;
const int lg = 18;
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 9 ms 4816 KB Output is correct
2 Correct 304 ms 14244 KB Output is correct
3 Correct 553 ms 14224 KB Output is correct
4 Correct 529 ms 14180 KB Output is correct
5 Correct 408 ms 14488 KB Output is correct
6 Correct 155 ms 14160 KB Output is correct
7 Correct 529 ms 14216 KB Output is correct
8 Correct 547 ms 14352 KB Output is correct
9 Correct 414 ms 14488 KB Output is correct
10 Correct 157 ms 14268 KB Output is correct
11 Correct 518 ms 14172 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Runtime error 353 ms 87972 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4816 KB Output is correct
2 Correct 304 ms 14244 KB Output is correct
3 Correct 553 ms 14224 KB Output is correct
4 Correct 529 ms 14180 KB Output is correct
5 Correct 408 ms 14488 KB Output is correct
6 Correct 155 ms 14160 KB Output is correct
7 Correct 529 ms 14216 KB Output is correct
8 Correct 547 ms 14352 KB Output is correct
9 Correct 414 ms 14488 KB Output is correct
10 Correct 157 ms 14268 KB Output is correct
11 Correct 518 ms 14172 KB Output is correct
12 Correct 3 ms 4436 KB Output is correct
13 Runtime error 353 ms 87972 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -