oj.uz

Submission #928293

# Submission time Handle Problem Language Result Execution time Memory
928293 2024-02-16T07:27:11 Z oblantis Factories (JOI14_factories) C++17
100 / 100
 3917 ms 222808 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 = 1e16;
const int mod = 1e9+7;
const int maxn = 5e5 + 1;
#include "factories.h"
int dp[maxn], up[maxn][20], sz[maxn], cup[maxn];
ll p[maxn], dst[maxn], tc[maxn][20];
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);
		}
	}
	sz[v] = -1;
	for(auto i : g[v]){
		if(sz[i.ff] != -1){
			cup[cd(i.ff, sz[i.ff])] = v;
		}
	}
	return v;
}
void dist(int x, int y, ll& q){
	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){
		q = p[x] - p[a] + p[y] - p[a];
		return;
	}
	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];
	q = p[x] - p[a] + p[y] - p[a];
}
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]});
	}
	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];
	}
	cup[cd(0, n)] = -1;
	for(int i = 0; i < n; i++){
		dst[i] = inf;
		for(int j = 0, puc = i; puc != -1; j++){
			dist(i, puc, tc[i][j]);
			puc = cup[puc];
		}
	}
}
long long Query(int s, int x[], int t, int y[]) {
	ll ret = inf;
	for(int i = 0; i < s; i++){
		int go = x[i];
		for(int j = 0; j < 20 && go != -1; j++){
			if(dst[go] == inf)rst.pb(go);
			dst[go] = min(dst[go], tc[x[i]][j]);
			go = cup[go];
		}
	}
	for(int i = 0; i < t; i++){
		int go = y[i];
		for(int j = 0; j < 20 && go != -1; j++){
			ret = min(ret, dst[go] + tc[y[i]][j]);
			go = cup[go];
		}
	}
	for(auto i : rst)dst[i] = inf;
	rst.clear();
	return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37468 KB Output is correct
2 Correct 205 ms 44160 KB Output is correct
3 Correct 218 ms 44168 KB Output is correct
4 Correct 202 ms 44368 KB Output is correct
5 Correct 225 ms 44676 KB Output is correct
6 Correct 147 ms 44168 KB Output is correct
7 Correct 216 ms 44380 KB Output is correct
8 Correct 216 ms 44372 KB Output is correct
9 Correct 223 ms 44692 KB Output is correct
10 Correct 153 ms 44368 KB Output is correct
11 Correct 219 ms 44424 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 37468 KB Output is correct
2 Correct 1045 ms 185280 KB Output is correct
3 Correct 2217 ms 189848 KB Output is correct
4 Correct 443 ms 185928 KB Output is correct
5 Correct 3586 ms 222808 KB Output is correct
6 Correct 2428 ms 189900 KB Output is correct
7 Correct 559 ms 77576 KB Output is correct
8 Correct 234 ms 77100 KB Output is correct
9 Correct 688 ms 81536 KB Output is correct
10 Correct 554 ms 77908 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37468 KB Output is correct
2 Correct 205 ms 44160 KB Output is correct
3 Correct 218 ms 44168 KB Output is correct
4 Correct 202 ms 44368 KB Output is correct
5 Correct 225 ms 44676 KB Output is correct
6 Correct 147 ms 44168 KB Output is correct
7 Correct 216 ms 44380 KB Output is correct
8 Correct 216 ms 44372 KB Output is correct
9 Correct 223 ms 44692 KB Output is correct
10 Correct 153 ms 44368 KB Output is correct
11 Correct 219 ms 44424 KB Output is correct
12 Correct 9 ms 37468 KB Output is correct
13 Correct 1045 ms 185280 KB Output is correct
14 Correct 2217 ms 189848 KB Output is correct
15 Correct 443 ms 185928 KB Output is correct
16 Correct 3586 ms 222808 KB Output is correct
17 Correct 2428 ms 189900 KB Output is correct
18 Correct 559 ms 77576 KB Output is correct
19 Correct 234 ms 77100 KB Output is correct
20 Correct 688 ms 81536 KB Output is correct
21 Correct 554 ms 77908 KB Output is correct
22 Correct 1186 ms 185036 KB Output is correct
23 Correct 1261 ms 186344 KB Output is correct
24 Correct 2541 ms 188536 KB Output is correct
25 Correct 2545 ms 191032 KB Output is correct
26 Correct 2685 ms 188504 KB Output is correct
27 Correct 3917 ms 215124 KB Output is correct
28 Correct 557 ms 211060 KB Output is correct
29 Correct 2525 ms 212384 KB Output is correct
30 Correct 2520 ms 211440 KB Output is correct
31 Correct 2629 ms 212512 KB Output is correct
32 Correct 646 ms 96720 KB Output is correct
33 Correct 239 ms 91852 KB Output is correct
34 Correct 454 ms 89756 KB Output is correct
35 Correct 393 ms 89944 KB Output is correct
36 Correct 614 ms 90704 KB Output is correct
37 Correct 545 ms 90452 KB Output is correct