답안 #65787 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65787	2018-08-08T18:21:54 Z	reality	공장들 (JOI14_factories)	C++17	100 / 100	7933 ms	466792 KB

factories

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #65787

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 18.0 / 18.0

Subtask #3 67.0 / 67.0

Subtask #1
15.0 / 15.0

Subtask #2
18.0 / 18.0

Subtask #3
67.0 / 67.0