oj.uz

Submission #928274

# Submission time Handle Problem Language Result Execution time Memory
928274 2024-02-16T06:42:23 Z oblantis Factories (JOI14_factories) C++17
33 / 100
 8000 ms 160508 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];
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;
}
void upd(int v, int i){
	if(v == -1)return;
	if(dst[v] == inf){
		rst.pb(v);
	}
	ll path;
	dist(i, v, path);
	dst[v] = min(dst[v], path);
	upd(cup[v], i);
}
void get(int v, int i, ll& ret){
	if(v == -1)return;
	ll path;
	dist(i, v, path);
	ret = min(ret, path + dst[v]);
	get(cup[v], i, ret);
}
long long Query(int s, int x[], int t, int y[]) {
	ll ret = inf;
	for(int i = 0; i < s; i++){
		upd(x[i], x[i]);
	}
	for(int i = 0; i < t; i++){
		get(y[i], y[i], ret);
	}
	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 16 ms 35420 KB Output is correct
2 Correct 502 ms 40264 KB Output is correct
3 Correct 1203 ms 40284 KB Output is correct
4 Correct 1155 ms 40308 KB Output is correct
5 Correct 1423 ms 40644 KB Output is correct
6 Correct 185 ms 40068 KB Output is correct
7 Correct 1157 ms 40340 KB Output is correct
8 Correct 1238 ms 40296 KB Output is correct
9 Correct 1454 ms 40652 KB Output is correct
10 Correct 205 ms 40072 KB Output is correct
11 Correct 1195 ms 40276 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35420 KB Output is correct
2 Correct 1542 ms 107108 KB Output is correct
3 Correct 4026 ms 111496 KB Output is correct
4 Correct 567 ms 107804 KB Output is correct
5 Correct 7228 ms 144632 KB Output is correct
6 Correct 4835 ms 111380 KB Output is correct
7 Correct 3219 ms 57504 KB Output is correct
8 Correct 317 ms 56932 KB Output is correct
9 Correct 3904 ms 61376 KB Output is correct
10 Correct 2874 ms 57872 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35420 KB Output is correct
2 Correct 502 ms 40264 KB Output is correct
3 Correct 1203 ms 40284 KB Output is correct
4 Correct 1155 ms 40308 KB Output is correct
5 Correct 1423 ms 40644 KB Output is correct
6 Correct 185 ms 40068 KB Output is correct
7 Correct 1157 ms 40340 KB Output is correct
8 Correct 1238 ms 40296 KB Output is correct
9 Correct 1454 ms 40652 KB Output is correct
10 Correct 205 ms 40072 KB Output is correct
11 Correct 1195 ms 40276 KB Output is correct
12 Correct 9 ms 35420 KB Output is correct
13 Correct 1542 ms 107108 KB Output is correct
14 Correct 4026 ms 111496 KB Output is correct
15 Correct 567 ms 107804 KB Output is correct
16 Correct 7228 ms 144632 KB Output is correct
17 Correct 4835 ms 111380 KB Output is correct
18 Correct 3219 ms 57504 KB Output is correct
19 Correct 317 ms 56932 KB Output is correct
20 Correct 3904 ms 61376 KB Output is correct
21 Correct 2874 ms 57872 KB Output is correct
22 Correct 2451 ms 106892 KB Output is correct
23 Correct 2332 ms 107628 KB Output is correct
24 Correct 7509 ms 110132 KB Output is correct
25 Correct 7440 ms 112284 KB Output is correct
26 Correct 7773 ms 134500 KB Output is correct
27 Execution timed out 8012 ms 160508 KB Time limit exceeded
28 Halted 0 ms 0 KB -