oj.uz

Submission #370281

# Submission time Handle Problem Language Result Execution time Memory
370281 2021-02-23T16:14:12 Z Return_0 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 229464 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,tune=native")

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

#ifndef SINA
#include "factories.h"
#endif

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], bn [N];
vector <pll> adj [N];
bool hide [N];

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

inline ll find_centroid (ll v, cl &_n, ll pr = -1) {
	for (ll i = 0, u; i < SZ(adj[v]); i++) {
		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, w] : adj[v]) if (!hide[u] && u != pr) dist[u][cur2] = dist[v][cur2] + w, dfs(u, 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, w] : adj[v]) if (!hide[u]) dist[u][lev] = w, dfs(u, v);
	hide[v] = 1;
	for (auto [u, w] : adj[v]) if (!hide[u]) centroid_decomposition(u, lev + 1);
}

void Init (ll N, ll A[], ll B[], ll D[]) {
	memset(rn, 61, sizeof rn);
	memset(bn, 61, sizeof bn);
	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; i < S; i++) for (ll v = X[i], lev = wcen[v]; ~lev; lev--) {
		v = cen[v][lev];
		rn[v] = min(rn[v], dist[X[i]][lev]);
	}
	for (ll i = 0; i < T; i++) for (ll v = Y[i], lev = wcen[v]; ~lev; lev--) {
		v = cen[v][lev];
		bn[v] = min(bn[v], dist[Y[i]][lev]);
		ans = min(ans, rn[v] + bn[v]);
	}

	for (ll i = 0; i < S; i++) for (ll v = X[i], lev = wcen[v]; ~lev; lev--) {
		v = cen[v][lev];
		rn[v] = inf;
	}
	for (ll i = 0; i < T; i++) for (ll v = Y[i], lev = wcen[v]; ~lev; lev--) {
		v = cen[v][lev];
		bn[v] = inf;
	}

	return ans;
}

#ifdef SINA
ll A [100], B [100], D[100];
int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll _n, q;
	cin>> _n >> q;
	for (ll i = 0; i < _n - 1; i++) {
		cin>> A[i] >> B[i] >> D[i];
	}

	Init(_n, A, B, D);

	while (q--) {
		ll s, t;
		cin>> s >> t;
		for (ll i = 0; i < s; i++) cin>> A[i];
		for (ll i = 0; i < t; i++) cin>> B[i];
		cout<< Query(s, A, t, B) << '\n';
	}

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	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

*/
#endif

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20588 KB Output is correct
2 Correct 546 ms 38836 KB Output is correct
3 Correct 603 ms 38864 KB Output is correct
4 Correct 608 ms 38892 KB Output is correct
5 Correct 683 ms 39264 KB Output is correct
6 Correct 375 ms 38852 KB Output is correct
7 Correct 612 ms 39096 KB Output is correct
8 Correct 576 ms 39020 KB Output is correct
9 Correct 694 ms 39400 KB Output is correct
10 Correct 378 ms 38864 KB Output is correct
11 Correct 574 ms 38940 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20204 KB Output is correct
2 Correct 3109 ms 191868 KB Output is correct
3 Correct 4540 ms 194532 KB Output is correct
4 Correct 1010 ms 192212 KB Output is correct
5 Correct 5976 ms 229464 KB Output is correct
6 Correct 4722 ms 196368 KB Output is correct
7 Correct 2146 ms 73192 KB Output is correct
8 Correct 724 ms 73668 KB Output is correct
9 Correct 2607 ms 78236 KB Output is correct
10 Correct 2148 ms 74760 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20588 KB Output is correct
2 Correct 546 ms 38836 KB Output is correct
3 Correct 603 ms 38864 KB Output is correct
4 Correct 608 ms 38892 KB Output is correct
5 Correct 683 ms 39264 KB Output is correct
6 Correct 375 ms 38852 KB Output is correct
7 Correct 612 ms 39096 KB Output is correct
8 Correct 576 ms 39020 KB Output is correct
9 Correct 694 ms 39400 KB Output is correct
10 Correct 378 ms 38864 KB Output is correct
11 Correct 574 ms 38940 KB Output is correct
12 Correct 14 ms 20204 KB Output is correct
13 Correct 3109 ms 191868 KB Output is correct
14 Correct 4540 ms 194532 KB Output is correct
15 Correct 1010 ms 192212 KB Output is correct
16 Correct 5976 ms 229464 KB Output is correct
17 Correct 4722 ms 196368 KB Output is correct
18 Correct 2146 ms 73192 KB Output is correct
19 Correct 724 ms 73668 KB Output is correct
20 Correct 2607 ms 78236 KB Output is correct
21 Correct 2148 ms 74760 KB Output is correct
22 Correct 4862 ms 180588 KB Output is correct
23 Correct 4577 ms 182852 KB Output is correct
24 Correct 7061 ms 183728 KB Output is correct
25 Correct 6862 ms 187336 KB Output is correct
26 Correct 6974 ms 184064 KB Output is correct
27 Execution timed out 8042 ms 209656 KB Time limit exceeded
28 Halted 0 ms 0 KB -