oj.uz

Submission #370764

# Submission time Handle Problem Language Result Execution time Memory
370764 2021-02-24T14:47:00 Z Return_0 Factories (JOI14_factories) C++17
100 / 100
 7433 ms 216376 KB 
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#include "factories.h"

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

const long long inf = sizeof(long long) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 5e5 + 7, lg = 20;

ll sz [N], cen [N][lg], wcen [N], n, cur1, cur2;
long long dist [N][lg], rn [N];
vector <pll> adj [N];
bool hide [N];

ll plant (cl &v, cl &pr = -1) {
	sz[v] = 1;
	for (auto &u : adj[v]) if (!hide[u.fr] && u.fr != pr) sz[v] += plant(u.fr, v);
	return sz[v];
}

inline ll find_centroid (ll v, cl &_n, ll pr = -1) {
	for (ll i = 0; i < SZ(adj[v]); i++) {
		ll &u = adj[v][i].fr;
		if (sz[u] << 1 > _n && !hide[u] && u != pr) pr = v, v = u, i = -1;
	}
	return v;
}

void dfs (cl &v, cl &pr) {
	cen[v][cur2] = cur1;
	for (auto &u : adj[v]) if (!hide[u.fr] && u.fr != pr) dist[u.fr][cur2] = dist[v][cur2] + u.sc, dfs(u.fr, v);
}

void centroid_decomposition (ll v = 0, cl &lev = 0) {
	v = find_centroid(v, plant(v)); cur1 = v; cur2 = lev;
	wcen[v] = lev;
	cen[v][lev] = v;
	for (auto &u : adj[v]) if (!hide[u.fr]) dist[u.fr][lev] = u.sc, dfs(u.fr, v);
	hide[v] = 1;
	for (auto &u : adj[v]) if (!hide[u.fr]) centroid_decomposition(u.fr, lev + 1);
}

void Init (ll N, ll A[], ll B[], ll D[]) {
	memset(rn, 61, sizeof rn);
	n = N;
	for (ll i = 0; i < n - 1; i++) adj[A[i]].push_back({B[i], D[i]}), adj[B[i]].push_back({A[i], D[i]});
	centroid_decomposition();
}

long long Query (ll S, ll X[], ll T, ll Y[]) {
	long long ans = inf;
 
	for (ll i = 0, u; i < S; i++) {
		u = X[i];
		for (ll v = u, lev = wcen[v]; ~lev; lev--) {
			v = cen[v][lev];
			rn[v] = min(rn[v], dist[u][lev]);
		}
	}
	for (ll i = 0, u; i < T; i++) {
		u = Y[i];
		for (ll v = u, lev = wcen[v]; ~lev; lev--) {
			v = cen[v][lev];
			ans = min(ans, rn[v] + dist[u][lev]);
		}
	}
 
	for (ll i = 0; i < S; i++) for (ll v = X[i], lev = wcen[v]; ~lev; lev--) {
		v = cen[v][lev];
		rn[v] = inf;
	}

	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16620 KB Output is correct
2 Correct 431 ms 35108 KB Output is correct
3 Correct 527 ms 35052 KB Output is correct
4 Correct 498 ms 35052 KB Output is correct
5 Correct 541 ms 35316 KB Output is correct
6 Correct 329 ms 35092 KB Output is correct
7 Correct 540 ms 35052 KB Output is correct
8 Correct 484 ms 35052 KB Output is correct
9 Correct 544 ms 35460 KB Output is correct
10 Correct 356 ms 34924 KB Output is correct
11 Correct 479 ms 35052 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16364 KB Output is correct
2 Correct 2696 ms 188012 KB Output is correct
3 Correct 4080 ms 188728 KB Output is correct
4 Correct 966 ms 188372 KB Output is correct
5 Correct 5573 ms 212352 KB Output is correct
6 Correct 4164 ms 191056 KB Output is correct
7 Correct 1740 ms 68956 KB Output is correct
8 Correct 621 ms 69872 KB Output is correct
9 Correct 2243 ms 72940 KB Output is correct
10 Correct 1780 ms 70396 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16620 KB Output is correct
2 Correct 431 ms 35108 KB Output is correct
3 Correct 527 ms 35052 KB Output is correct
4 Correct 498 ms 35052 KB Output is correct
5 Correct 541 ms 35316 KB Output is correct
6 Correct 329 ms 35092 KB Output is correct
7 Correct 540 ms 35052 KB Output is correct
8 Correct 484 ms 35052 KB Output is correct
9 Correct 544 ms 35460 KB Output is correct
10 Correct 356 ms 34924 KB Output is correct
11 Correct 479 ms 35052 KB Output is correct
12 Correct 13 ms 16364 KB Output is correct
13 Correct 2696 ms 188012 KB Output is correct
14 Correct 4080 ms 188728 KB Output is correct
15 Correct 966 ms 188372 KB Output is correct
16 Correct 5573 ms 212352 KB Output is correct
17 Correct 4164 ms 191056 KB Output is correct
18 Correct 1740 ms 68956 KB Output is correct
19 Correct 621 ms 69872 KB Output is correct
20 Correct 2243 ms 72940 KB Output is correct
21 Correct 1780 ms 70396 KB Output is correct
22 Correct 3846 ms 195156 KB Output is correct
23 Correct 3899 ms 198028 KB Output is correct
24 Correct 5920 ms 197236 KB Output is correct
25 Correct 5748 ms 201004 KB Output is correct
26 Correct 5604 ms 197100 KB Output is correct
27 Correct 7433 ms 216376 KB Output is correct
28 Correct 1364 ms 198964 KB Output is correct
29 Correct 5475 ms 197180 KB Output is correct
30 Correct 5444 ms 196816 KB Output is correct
31 Correct 5392 ms 197324 KB Output is correct
32 Correct 2320 ms 73696 KB Output is correct
33 Correct 683 ms 70496 KB Output is correct
34 Correct 1365 ms 66924 KB Output is correct
35 Correct 1355 ms 66924 KB Output is correct
36 Correct 1831 ms 67308 KB Output is correct
37 Correct 1841 ms 67436 KB Output is correct