oj.uz

Submission #549997

# Submission time Handle Problem Language Result Execution time Memory
549997 2022-04-17T03:44:43 Z David1425 Factories (JOI14_factories) C++17
100 / 100
 4962 ms 214760 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("O3")

using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define ppb pop_back
#define all(x) (x).begin(),(x).end()
#define sz(x) int((x).size())
#define MEM(x, v) memset(x, v, sizeof(x))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
template<typename T> using reverse_pq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename CMP> using ordered_set = tree<T, null_type, CMP, rb_tree_tag, tree_order_statistics_node_update>;

void si() {}
template<typename T, typename... U>
void si(T& x, U&... u) {char _;int neg=1;do{while((x=getchar())<'0'&&(x!='-')){};if(x=='-'){neg=-1;x=getchar();}for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0);x*=neg;si(u...);}

template<typename T, typename U> typename common_type<T, U>::type min(T a, U b) { return (((a) < (b)) ? (a) : (b)); }
template<typename T, typename U> typename common_type<T, U>::type max(T a, U b) { return (((a) > (b)) ? (a) : (b)); }
template<typename T, typename U> typename common_type<T, U>::type minv(T a, U b) { return min(a, b); }
template<typename T, typename... U> typename common_type<T, U...>::type minv(T a, U... b) { return min(a, minv(b...)); }
template<typename T, typename U> typename common_type<T, U>::type maxv(T a, U b) { return max(a, b); }
template<typename T, typename... U> typename common_type<T, U...>::type maxv(T a, U... b) { return max(a, maxv(b...)); }

int lg2(long long x) { return 63 - __builtin_clzll(x); }
int lg2(int x) { return 31 - __builtin_clz(x); }

mt19937 rng(uint64_t(new char)+chrono::steady_clock::now().time_since_epoch().count());

const ll MOD = 1e9+7;
const ll HASH = 131;
const int MM = 5e5+5;

int n;
vector<pii> adj[MM];

vi s(MM);
vector<bool> vis(MM);
void dfs1(int u, int p) {
	s[u] = 1;
	for (auto [v,w] : adj[u]) {
		if (v != p && !vis[v]) {
			dfs1(v,u);
			s[u] += s[v];
		}
	}
}

int centroid(int u, int p, int x) {
	for (auto [v,w] : adj[u]) {
		if (!vis[v] && v != p && s[v]*2 > x) return centroid(v,u,x);
	}
	return u;
}

vl dep[MM];
void dfs2(int u, int p, ll d) {
	dep[u].pb(d);
	for (auto [v,w] : adj[u]) {
		if (v != p && !vis[v]) {
			dfs2(v, u, d+w);
		}
	}
}

vi par(MM,-1);
void search(int u, int p) {
	dfs1(u,p);
	u = centroid(u,-1,s[u]);
	par[u] = p;
	vis[u] = 1;
	dfs2(u,p,0);
	
	for (auto [v,w] : adj[u]) {
		if (!vis[v]) {
			search(v,u);
		}
	}
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < N-1; i++) {
		adj[A[i]].pb({B[i],D[i]});
		adj[B[i]].pb({A[i],D[i]});
		// cout << A[i] << " " << B[i] << " " << D[i] << "\n";
	}
	search(0,-1);
	for (int i = 0; i < n; i++) reverse(all(dep[i]));
	// fill(vis.begin(), vis.begin()+N,0);
	// fill(all(vis),0);
}

vl res(MM, LINF);
ll Query(int s, int x[], int t, int y[]) {
	ll ans = LINF;
	for (int i = 0; i < s; i++) {
		for (int j = x[i], pos = 0; j != -1; j = par[j], pos++) {
			res[j] = min(res[j], dep[x[i]][pos]);
		}
	}
	for (int i = 0; i < t; i++) {
		for (int j = y[i], pos = 0; j != -1; j = par[j], pos++) {
			ans = min(ans, res[j]+dep[y[i]][pos]);
		}
	}
	for (int i = 0; i < s; i++) for (int j = x[i]; j != -1; j = par[j]) res[j] = LINF;
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31956 KB Output is correct
2 Correct 295 ms 49836 KB Output is correct
3 Correct 337 ms 50176 KB Output is correct
4 Correct 290 ms 50016 KB Output is correct
5 Correct 327 ms 50316 KB Output is correct
6 Correct 244 ms 49504 KB Output is correct
7 Correct 301 ms 49988 KB Output is correct
8 Correct 339 ms 50068 KB Output is correct
9 Correct 308 ms 50348 KB Output is correct
10 Correct 214 ms 49492 KB Output is correct
11 Correct 311 ms 50008 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31804 KB Output is correct
2 Correct 2325 ms 130948 KB Output is correct
3 Correct 3251 ms 165996 KB Output is correct
4 Correct 732 ms 80320 KB Output is correct
5 Correct 4310 ms 214760 KB Output is correct
6 Correct 3520 ms 167028 KB Output is correct
7 Correct 951 ms 74388 KB Output is correct
8 Correct 324 ms 64152 KB Output is correct
9 Correct 1082 ms 82340 KB Output is correct
10 Correct 954 ms 76008 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31956 KB Output is correct
2 Correct 295 ms 49836 KB Output is correct
3 Correct 337 ms 50176 KB Output is correct
4 Correct 290 ms 50016 KB Output is correct
5 Correct 327 ms 50316 KB Output is correct
6 Correct 244 ms 49504 KB Output is correct
7 Correct 301 ms 49988 KB Output is correct
8 Correct 339 ms 50068 KB Output is correct
9 Correct 308 ms 50348 KB Output is correct
10 Correct 214 ms 49492 KB Output is correct
11 Correct 311 ms 50008 KB Output is correct
12 Correct 18 ms 31804 KB Output is correct
13 Correct 2325 ms 130948 KB Output is correct
14 Correct 3251 ms 165996 KB Output is correct
15 Correct 732 ms 80320 KB Output is correct
16 Correct 4310 ms 214760 KB Output is correct
17 Correct 3520 ms 167028 KB Output is correct
18 Correct 951 ms 74388 KB Output is correct
19 Correct 324 ms 64152 KB Output is correct
20 Correct 1082 ms 82340 KB Output is correct
21 Correct 954 ms 76008 KB Output is correct
22 Correct 2629 ms 131064 KB Output is correct
23 Correct 2679 ms 134352 KB Output is correct
24 Correct 4132 ms 168032 KB Output is correct
25 Correct 4113 ms 171156 KB Output is correct
26 Correct 3996 ms 168900 KB Output is correct
27 Correct 4962 ms 214128 KB Output is correct
28 Correct 892 ms 84848 KB Output is correct
29 Correct 4021 ms 168164 KB Output is correct
30 Correct 4098 ms 167736 KB Output is correct
31 Correct 4110 ms 168784 KB Output is correct
32 Correct 1181 ms 83180 KB Output is correct
33 Correct 328 ms 64588 KB Output is correct
34 Correct 691 ms 69940 KB Output is correct
35 Correct 743 ms 70284 KB Output is correct
36 Correct 1002 ms 72840 KB Output is correct
37 Correct 984 ms 72796 KB Output is correct