oj.uz

Submission #928263

# Submission time Handle Problem Language Result Execution time Memory
928263 2024-02-16T06:25:46 Z oblantis Factories (JOI14_factories) C++17
33 / 100
 8000 ms 156560 KB 
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll inf = 1e15;
const int mod = 1e9+7;
const int maxn = 5e5 + 3;
#include "factories.h"
int dp[maxn], up[maxn][20], sz[maxn], cup[maxn];
ll p[maxn], dst[maxn];
vt<pii> g[maxn];
vt<int> rst;
bool first;
void dfs(int v){
	sz[v] = 1;
	for(auto i : g[v]){
		if(i.ff != up[v][0]){
			up[i.ff][0] = v;
			dp[i.ff] = dp[v] + 1;
			p[i.ff] = p[v] + i.ss;
			dfs(i.ff);
			sz[v] += sz[i.ff];
		}
	}
}
int cd(int v, int m){
	for(auto i : g[v]){
		if(sz[i.ff] > m / 2){
			sz[v] = m - sz[i.ff];
			return cd(i.ff, m);
		}
	}
	if(!first){
		first = 1;
		cup[v] = -1;
	}
	//cout << v << ' ';
	sz[v] = -1;
	for(auto i : g[v]){
		if(sz[i.ff] != -1){
			cup[cd(i.ff, sz[i.ff])] = v;
		}
	}
	return v;
}
ll dist(int x, int y){
	if(dp[x] > dp[y])swap(x, y);
	int a = x, b = y;
	for(int j = 19; j >= 0; j--){
		if(((dp[b] - dp[a]) >> j) & 1){
			b = up[b][j];
		}
	}
	if(a == b){
		ll q = p[x] - p[a] + p[y] - p[a];
		return q;
	}
	for(int j = 19; j >= 0; j--){
		if(up[b][j] != up[a][j]){
			a = up[a][j], b = up[b][j];
		}
	}
	a = up[a][0];
	ll q = p[x] - p[a] + p[y] - p[a];
	return q;
}
void Init(int n, int a[], int b[], int d[]) {
	for(int i = 0; i < n - 1; i++){
		g[a[i]].pb({b[i], d[i]});
		g[b[i]].pb({a[i], d[i]});
	}
	first = 0;
	dfs(0);
	for(int j = 1; j < 20; j++){
		for(int i = 0; i < n; i++)up[i][j] = up[up[i][j - 1]][j - 1];
	}
	cd(0, n);
	for(int i = 0; i < n; i++)dst[i] = inf;
}
long long Query(int s, int x[], int t, int y[]) {
	ll ret = inf;
	for(int i = 0; i < s; i++){
		int par = x[i];
		while(par != -1){
			if(dst[par] == inf)rst.pb(par);
			dst[par] = min(dst[par], dist(x[i], par));
			par = cup[par];
		}
	}
	for(int i = 0; i < t; i++){
		int par = y[i];
		while(par != -1){
			ret = min(ret, dst[par] + dist(par, y[i]));
			par = cup[par];
		}
	}
	for(auto i : rst)dst[i] = inf;
	rst.clear();
	return ret;
}

//void solve() {
	//int n, q;
	//cin >> n >> q;
	//int a[n - 1], b[n - 1], d[n - 1];
	//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';
	//}
//}
//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int times = 1;
	////cin >> times;
	//for(int i = 1; i <= times; i++) {
		//solve();
	//}
	//return 0;
//}

//7 3
//0 1 4
//1 2 4
//2 3 5
//2 4 6
//4 5 5
//1 6 3
//2 2
//0 6
//3 4
//3 2
//0 1 3
//4 6
//1 1
//2
//5

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35416 KB Output is correct
2 Correct 561 ms 40272 KB Output is correct
3 Correct 1336 ms 40276 KB Output is correct
4 Correct 1299 ms 40336 KB Output is correct
5 Correct 1600 ms 40584 KB Output is correct
6 Correct 211 ms 40072 KB Output is correct
7 Correct 1277 ms 40276 KB Output is correct
8 Correct 1349 ms 40332 KB Output is correct
9 Correct 1658 ms 40580 KB Output is correct
10 Correct 202 ms 40276 KB Output is correct
11 Correct 1244 ms 40272 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35416 KB Output is correct
2 Correct 1636 ms 106784 KB Output is correct
3 Correct 4345 ms 128508 KB Output is correct
4 Correct 649 ms 126036 KB Output is correct
5 Correct 7400 ms 156560 KB Output is correct
6 Correct 4904 ms 129268 KB Output is correct
7 Correct 3318 ms 71192 KB Output is correct
8 Correct 328 ms 71108 KB Output is correct
9 Correct 4019 ms 74776 KB Output is correct
10 Correct 3243 ms 71692 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35416 KB Output is correct
2 Correct 561 ms 40272 KB Output is correct
3 Correct 1336 ms 40276 KB Output is correct
4 Correct 1299 ms 40336 KB Output is correct
5 Correct 1600 ms 40584 KB Output is correct
6 Correct 211 ms 40072 KB Output is correct
7 Correct 1277 ms 40276 KB Output is correct
8 Correct 1349 ms 40332 KB Output is correct
9 Correct 1658 ms 40580 KB Output is correct
10 Correct 202 ms 40276 KB Output is correct
11 Correct 1244 ms 40272 KB Output is correct
12 Correct 8 ms 35416 KB Output is correct
13 Correct 1636 ms 106784 KB Output is correct
14 Correct 4345 ms 128508 KB Output is correct
15 Correct 649 ms 126036 KB Output is correct
16 Correct 7400 ms 156560 KB Output is correct
17 Correct 4904 ms 129268 KB Output is correct
18 Correct 3318 ms 71192 KB Output is correct
19 Correct 328 ms 71108 KB Output is correct
20 Correct 4019 ms 74776 KB Output is correct
21 Correct 3243 ms 71692 KB Output is correct
22 Correct 2568 ms 130964 KB Output is correct
23 Correct 2669 ms 132488 KB Output is correct
24 Correct 7976 ms 133880 KB Output is correct
25 Execution timed out 8087 ms 136108 KB Time limit exceeded
26 Halted 0 ms 0 KB -