oj.uz

Submission #65776

# Submission time Handle Problem Language Result Execution time Memory
65776 2018-08-08T17:57:32 Z reality Factories (JOI14_factories) C++17
33 / 100
 8000 ms 239056 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];
 
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]);
	set < int > ss;
	for (auto it : a) {
		int node = it;
		while (node >= 0) {
			ss.insert(in[nxt[node]]);
			ss.insert(in[node]);
			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) {
			ss.insert(in[nxt[node]]);
			ss.insert(in[node]);
			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];
	for (auto i : ss) {
		for (auto it : add[i]) {
			S[it.se].insert(it.fi);
		}
		if (!S[0].empty() && !S[1].empty()) {
			smin(ans,*S[0].begin() + *S[1].begin() - 2 * D[rin[i]]);
		}
		for (auto it : del[i]) {
			S[it.se].erase(S[it.se].find(it.fi));
		}
		add[i].clear();
		del[i].clear();
	}
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 141544 KB Output is correct
2 Correct 4465 ms 150872 KB Output is correct
3 Correct 3514 ms 150872 KB Output is correct
4 Correct 4155 ms 151272 KB Output is correct
5 Correct 2146 ms 151272 KB Output is correct
6 Correct 2423 ms 151272 KB Output is correct
7 Correct 3281 ms 151272 KB Output is correct
8 Correct 3153 ms 151272 KB Output is correct
9 Correct 1836 ms 151272 KB Output is correct
10 Correct 2572 ms 151272 KB Output is correct
11 Correct 3236 ms 151272 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 151272 KB Output is correct
2 Correct 6736 ms 211472 KB Output is correct
3 Correct 4377 ms 211472 KB Output is correct
4 Correct 2561 ms 217300 KB Output is correct
5 Correct 2692 ms 233740 KB Output is correct
6 Correct 4655 ms 233740 KB Output is correct
7 Correct 5116 ms 233740 KB Output is correct
8 Correct 2752 ms 233740 KB Output is correct
9 Correct 2372 ms 233740 KB Output is correct
10 Correct 4457 ms 233740 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 141544 KB Output is correct
2 Correct 4465 ms 150872 KB Output is correct
3 Correct 3514 ms 150872 KB Output is correct
4 Correct 4155 ms 151272 KB Output is correct
5 Correct 2146 ms 151272 KB Output is correct
6 Correct 2423 ms 151272 KB Output is correct
7 Correct 3281 ms 151272 KB Output is correct
8 Correct 3153 ms 151272 KB Output is correct
9 Correct 1836 ms 151272 KB Output is correct
10 Correct 2572 ms 151272 KB Output is correct
11 Correct 3236 ms 151272 KB Output is correct
12 Correct 135 ms 151272 KB Output is correct
13 Correct 6736 ms 211472 KB Output is correct
14 Correct 4377 ms 211472 KB Output is correct
15 Correct 2561 ms 217300 KB Output is correct
16 Correct 2692 ms 233740 KB Output is correct
17 Correct 4655 ms 233740 KB Output is correct
18 Correct 5116 ms 233740 KB Output is correct
19 Correct 2752 ms 233740 KB Output is correct
20 Correct 2372 ms 233740 KB Output is correct
21 Correct 4457 ms 233740 KB Output is correct
22 Execution timed out 8048 ms 239056 KB Time limit exceeded
23 Halted 0 ms 0 KB -