oj.uz

Submission #798767

# Submission time Handle Problem Language Result Execution time Memory
798767 2023-07-31T03:54:18 Z OrazB Factories (JOI14_factories) C++14
15 / 100
 8000 ms 128288 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

const int N = 5e5+5;
const ll inf = 1e18;
int rem[N], sub[N], par[N], sp[N][20], lvl[N];
ll w[N], cur[N];
vector<pii> E[N];

void dfs(int nd, int pr){
	sub[nd] = 1;
	for (auto i : E[nd]){
		if (i.ff == pr or rem[i.ff]) continue;
		dfs(i.ff, nd);
		sub[nd] += sub[i.ff];
	}
}
int centroid(int nd, int pr, int sz){
	for (auto i : E[nd]){
		if (i.ff == pr or rem[i.ff]) continue;
		if (sub[i.ff]*2 > sz) return centroid(i.ff, nd, sz);
	}
	return nd;
}
void build(int nd, int pr){
	int centr = centroid(nd, 0, sub[nd]);
	rem[centr] = 1;
	par[centr] = pr;
	for (auto i : E[centr]){
		if (!rem[i.ff]){
			dfs(i.ff, 0);
			build(i.ff, centr);
		}
	}
}
void dfs2(int nd, int pr){
	sp[nd][0] = pr;
	for (auto i : E[nd]){
		if (i.ff == pr) continue;
		lvl[i.ff] = lvl[nd]+1;
		w[i.ff] = w[nd]+i.ss;
		dfs2(i.ff, nd);
	}
}
int LCA(int u, int v){
	if (lvl[u] < lvl[v]) swap(u, v);
	int diff = lvl[u]-lvl[v];
	for (int i = 19; i >= 0; i--){
		if (diff&(1<<i)) u = sp[u][i];
	}
	if (u == v) return v;
	for (int i = 19; i >= 0; i--){
		if (sp[u][i] != sp[v][i]){
			u = sp[u][i];
			v = sp[v][i];
		}
	}
	return sp[u][0];
}
ll dist(int u, int v){
	if (u == v) return 0ll;
	return w[u]+w[v]-2*w[LCA(u,v)];
}
void Init(int n, int A[], int B[], int D[]){
	for (int i = 0; i < n-1; i++){
		A[i]++;
		B[i]++;
		E[A[i]].pb({B[i], D[i]});
		E[B[i]].pb({A[i], D[i]});
	}
	dfs(1, 0);
	build(1, 0);
	dfs2(1, 0);
	for (int j = 1; j <= 19; j++){
		for (int i = 1; i <= n; i++) sp[i][j] = sp[sp[i][j-1]][j-1];
	}
	for (int i = 1; i <= n; i++) cur[i] = inf;
}
void remv(int nd){
	while(nd){
		cur[nd] = inf;
		nd = par[nd];
	}
}
void paint(int nd){
	int u = nd;
	while(u){
		cur[u] = min(cur[u], dist(u, nd));
		u = par[u];
	}
}
ll find(int nd){
	ll mn = inf;
	int u = nd;
	while(u){
		mn = min(mn, dist(u, nd)+cur[u]);
		u = par[u];
	}
	return mn;
}
ll Query(int S, int X[], int T, int Y[]){
	for (int i = 0; i < S; i++){
		X[i]++;
		paint(X[i]);
	}
	ll ans = inf;
	for (int i = 0; i < T; i++){
		Y[i]++;
		ans = min(ans, find(Y[i]));
	}
	for (int i = 0; i < S; i++) remv(X[i]);
	return ans;
}


// int main ()
// {
// 	int n, q;
// 	cin >> n >> q;
// 	int A[n], B[n], D[n];
// 	for (int i = 0; i < n-1; i++){
// 		cin >> A[i] >> B[i] >> D[i];
// 	}
// 	Init(n, A, B, D);
// 	for (int i = 0; i < q; i++){
// 		int S, T;
// 		cin >> S >> T;
// 		int X[S], Y[T];
// 		for (int j = 0; j < S; j++) cin >> X[j];
// 		for (int j = 0; j < T; j++) cin >> Y[j];
// 		cout << Query(S, X, T, Y) << '\n';
// 	}
// }

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12628 KB Output is correct
2 Correct 495 ms 21660 KB Output is correct
3 Correct 1069 ms 22352 KB Output is correct
4 Correct 1038 ms 22244 KB Output is correct
5 Correct 1208 ms 22616 KB Output is correct
6 Correct 182 ms 22316 KB Output is correct
7 Correct 1059 ms 22248 KB Output is correct
8 Correct 1105 ms 22296 KB Output is correct
9 Correct 1203 ms 22544 KB Output is correct
10 Correct 187 ms 22248 KB Output is correct
11 Correct 1057 ms 22244 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12280 KB Output is correct
2 Correct 1843 ms 98712 KB Output is correct
3 Correct 4347 ms 101308 KB Output is correct
4 Correct 633 ms 99496 KB Output is correct
5 Execution timed out 8021 ms 128288 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12628 KB Output is correct
2 Correct 495 ms 21660 KB Output is correct
3 Correct 1069 ms 22352 KB Output is correct
4 Correct 1038 ms 22244 KB Output is correct
5 Correct 1208 ms 22616 KB Output is correct
6 Correct 182 ms 22316 KB Output is correct
7 Correct 1059 ms 22248 KB Output is correct
8 Correct 1105 ms 22296 KB Output is correct
9 Correct 1203 ms 22544 KB Output is correct
10 Correct 187 ms 22248 KB Output is correct
11 Correct 1057 ms 22244 KB Output is correct
12 Correct 7 ms 12280 KB Output is correct
13 Correct 1843 ms 98712 KB Output is correct
14 Correct 4347 ms 101308 KB Output is correct
15 Correct 633 ms 99496 KB Output is correct
16 Execution timed out 8021 ms 128288 KB Time limit exceeded
17 Halted 0 ms 0 KB -