oj.uz

Submission #65787

# Submission time Handle Problem Language Result Execution time Memory
65787 2018-08-08T18:21:54 Z reality Factories (JOI14_factories) C++17
100 / 100
 7933 ms 466792 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
 
int n;
 
const int N = 2e6 + 5;
 
vector < pii > g[N];
 
int * SZ;
 
void dfs_sz(int v = 0) {
	SZ[v] = 1;
	for (auto & u : g[v]) {
		if (SZ[u.fi] != -1)
			continue;
		dfs_sz(u.fi);
		SZ[v] += SZ[u.fi];
		if (SZ[u.fi] >= SZ[g[v][0].fi])
			swap(u, g[v][0]);
	}
}
 
int * in;
 
int * out;
 
int * rin;
 
int * nxt;
 
int * pr;
 
int Time = 0;
 
ll * D;
 
void dfs_hld(int v = 0) {
	in[v] = ++Time;
	rin[in[v]] = v;
	for (auto u : g[v]) {
		if (D[u.fi] != -1)
			continue;
		nxt[u.fi] = (u == g[v][0] ? nxt[v] : u.fi);
		D[u.fi] = u.se + D[v];
		pr[u.fi] = v;
		dfs_hld(u.fi);
	}
	out[v] = Time;
}
 
void Init(int NN, int A[], int B[], int DD[]) {
	n = NN;
	D = new ll[n + 5];
	pr = new int[n + 5];
	SZ = new int[n + 5];
	in = new int[n + 5];
	out = new int[n + 5];
	nxt = new int[n + 5];
	rin = new int[n + 5];
	for (int i = 0;i < n;++i) {
		g[A[i]].pb(mp(B[i],DD[i]));
		g[B[i]].pb(mp(A[i],DD[i]));
	}
	for (int i = 0;i < n;++i)
		SZ[i] = D[i] = -1;
	D[0] = 0;
	dfs_sz();
	dfs_hld();
	pr[0] = -1;
}
 
vector < pair < ll , int > > add[N],del[N];

int S1[N],S2[N],was[N];

long long Query(int SS, int X[], int T, int Y[]) {
	vi a,b;
	for (int i = 0;i < SS;++i)
		a.pb(X[i]);
	for (int i = 0;i < T;++i)
		b.pb(Y[i]);
	sort(all(a),[&](int x,int y) {
			return D[x] < D[y];
		});
	sort(all(b),[&](int x,int y) {
			return D[x] < D[y];
		});
	vi ss;
	auto ADD = [&](int ps) {
		if (!was[ps])
			ss.pb(ps);
		was[ps] = 1;
	};
	for (auto it : a) {
		int node = it;
		while (node >= 0 && !S1[in[node]]) {
			ADD(in[nxt[node]]);
			S1[in[nxt[node]]] = 1;
			ADD(in[node]);
			S1[in[node]] = 1;
			add[in[nxt[node]]].pb(mp(D[it],0));
			del[in[node]].pb(mp(D[it],0));
			node = pr[nxt[node]];
		}
	}
	for (auto it : b) {
		int node = it;
		while (node >= 0 && !S2[in[node]]) {
			ADD(in[nxt[node]]);
			S2[in[nxt[node]]] = 1;
			ADD(in[node]);
			S2[in[node]] = 1;
			add[in[nxt[node]]].pb(mp(D[it],1));
			del[in[node]].pb(mp(D[it],1));
			node = pr[nxt[node]];
		}
	}
	ll ans = 1e18;
	multiset < ll > S[2];
	ll mn[2] = {ans,ans};
	sort(all(ss));
	for (auto i : ss) {
		for (auto it : add[i]) {
			S[it.se].insert(it.fi);
			smin(mn[it.se],it.fi);
		}
		smin(ans,mn[0] + mn[1] - 2 * D[rin[i]]);
		for (auto it : del[i]) {
			S[it.se].erase(S[it.se].find(it.fi));
			if (mn[it.se] == it.fi) {
				if (S[it.se].empty()) {
					mn[it.se] = 1e18;
				} else {
					mn[it.se] = *S[it.se].begin();
				}
			}
		}
		add[i].clear();
		del[i].clear();
		S1[i] = S2[i] = was[i] = 0;
	}
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 141688 KB Output is correct
2 Correct 1188 ms 150216 KB Output is correct
3 Correct 1559 ms 150256 KB Output is correct
4 Correct 1329 ms 150640 KB Output is correct
5 Correct 1066 ms 150640 KB Output is correct
6 Correct 985 ms 150640 KB Output is correct
7 Correct 1592 ms 150640 KB Output is correct
8 Correct 1242 ms 150640 KB Output is correct
9 Correct 1120 ms 150860 KB Output is correct
10 Correct 918 ms 150860 KB Output is correct
11 Correct 1458 ms 150860 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 150860 KB Output is correct
2 Correct 6620 ms 218260 KB Output is correct
3 Correct 4481 ms 218260 KB Output is correct
4 Correct 2482 ms 223536 KB Output is correct
5 Correct 2585 ms 239676 KB Output is correct
6 Correct 4678 ms 239676 KB Output is correct
7 Correct 3289 ms 239676 KB Output is correct
8 Correct 2128 ms 239676 KB Output is correct
9 Correct 2020 ms 239676 KB Output is correct
10 Correct 3552 ms 239676 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 141688 KB Output is correct
2 Correct 1188 ms 150216 KB Output is correct
3 Correct 1559 ms 150256 KB Output is correct
4 Correct 1329 ms 150640 KB Output is correct
5 Correct 1066 ms 150640 KB Output is correct
6 Correct 985 ms 150640 KB Output is correct
7 Correct 1592 ms 150640 KB Output is correct
8 Correct 1242 ms 150640 KB Output is correct
9 Correct 1120 ms 150860 KB Output is correct
10 Correct 918 ms 150860 KB Output is correct
11 Correct 1458 ms 150860 KB Output is correct
12 Correct 124 ms 150860 KB Output is correct
13 Correct 6620 ms 218260 KB Output is correct
14 Correct 4481 ms 218260 KB Output is correct
15 Correct 2482 ms 223536 KB Output is correct
16 Correct 2585 ms 239676 KB Output is correct
17 Correct 4678 ms 239676 KB Output is correct
18 Correct 3289 ms 239676 KB Output is correct
19 Correct 2128 ms 239676 KB Output is correct
20 Correct 2020 ms 239676 KB Output is correct
21 Correct 3552 ms 239676 KB Output is correct
22 Correct 7315 ms 239676 KB Output is correct
23 Correct 7933 ms 249376 KB Output is correct
24 Correct 5280 ms 275724 KB Output is correct
25 Correct 5694 ms 303228 KB Output is correct
26 Correct 7153 ms 319000 KB Output is correct
27 Correct 3973 ms 361740 KB Output is correct
28 Correct 4188 ms 377648 KB Output is correct
29 Correct 7251 ms 392092 KB Output is correct
30 Correct 7611 ms 415536 KB Output is correct
31 Correct 7375 ms 440684 KB Output is correct
32 Correct 2280 ms 440684 KB Output is correct
33 Correct 2237 ms 440684 KB Output is correct
34 Correct 4373 ms 440684 KB Output is correct
35 Correct 4276 ms 440684 KB Output is correct
36 Correct 4197 ms 453480 KB Output is correct
37 Correct 3833 ms 466792 KB Output is correct