oj.uz

Submission #227061

# Submission time Handle Problem Language Result Execution time Memory
227061 2020-04-26T00:15:51 Z rqi Factories (JOI14_factories) C++14
100 / 100
 3635 ms 209488 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 

template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
template<class A, class B> str ts(pair<A,B> p);
template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(char c) { str s = ""; s += c; return s; }
str ts(str s) { return s; }
str ts(const char* s) { return (str)s; }
str ts(vector<bool> v) { 
	bool fst = 1; str res = "{";
	F0R(i,sz(v)) {
		if (!fst) res += ", ";
		fst = 0; res += ts(v[i]);
	}
	res += "}"; return res;
}
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class T> str ts(T v) {
	bool fst = 1; str res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += ts(x);
	}
	res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
	return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 



/**
 * Description: 1D range minimum query. Can also do queries 
 	* for any associative operation in $O(1)$ with D\&C
 * Source: KACTL
 * Verification: 
	* https://cses.fi/problemset/stats/1647/
	* http://wcipeg.com/problem/ioi1223
	* https://pastebin.com/ChpniVZL
 * Memory: O(N\log N)
 * Time: O(1)
 */

template<class T> struct RMQ { // floor(log_2(x))
	int level(int x) { return 31-__builtin_clz(x); } 
	vector<T> v; vector<vi> jmp;
	int comb(int a, int b) { // index of min
		return v[a]==v[b]?min(a,b):(v[a]<v[b]?a:b); } 
	void init(const vector<T>& _v) {
		v = _v; jmp = {vi(sz(v))}; iota(all(jmp[0]),0);
		for (int j = 1; 1<<j <= sz(v); ++j) {
			jmp.pb(vi(sz(v)-(1<<j)+1));
			F0R(i,sz(jmp[j])) jmp[j][i] = comb(jmp[j-1][i],
									jmp[j-1][i+(1<<(j-1))]);
		}
	}
	int index(int l, int r) { // get index of min element
		int d = level(r-l+1);
		return comb(jmp[d][l],jmp[d][r-(1<<d)+1]); }
	T query(int l, int r) { return v[index(l,r)]; }
};


/**
 * Description: Euler Tour LCA w/ O(1) query. Compress takes a subset $S$ 
 	* of nodes and computes the minimal subtree that contains all the nodes 
	* pairwise LCA's and compressing edges. Returns a list of (par, orig\_index) 
	* representing a tree rooted at 0. The root points to itself.
 * Source: USACO, Simon Lindholm (KACTL)
 * Verification: USACO Debug the Bugs
 	* https://codeforces.com/contest/1320/problem/E
 */

template<int SZ> struct LCA {
	int N, R = 1, depth[SZ], st[SZ];
	ll dist[SZ];
	vector<pair<int, ll>> adj[SZ]; vpi tmp; RMQ<pi> r;
	void ae(int u, int v, ll d) { adj[u].pb(mp(v, d)), adj[v].pb(mp(u, d)); }
	void dfs(int u, int prev, ll d = 0){
		st[u] = sz(tmp), depth[u] = depth[prev]+1;
		dist[u] = d;
		tmp.pb({depth[u],u});
		trav(v,adj[u]) if (v.f != prev) 
			dfs(v.f,u,d+v.s), tmp.pb({depth[u],u});
	}
	void init(int _N) { N = _N; dfs(R,0); r.init(tmp); }
	int lca(int u, int v){
		u = st[u], v = st[v]; if (u > v) swap(u,v);
		return r.query(u,v).s; }
	ll getDist(int u, int v) {
		return dist[u]+dist[v]-2*dist[lca(u,v)]; }
	vpi compress(vi S) {
		static vi rev; rev.rsz(N+1);
		auto cmp = [&](int a, int b) { return st[a] < st[b]; };
		sort(all(S),cmp);
		int m = sz(S)-1; F0R(i,m) S.pb(lca(S[i],S[i+1]));
		sort(all(S),cmp); S.erase(unique(all(S)),end(S));
		F0R(i,sz(S)) rev[S[i]] = i;
		vpi ret = {pi(0,S[0])};
		F0R(i,sz(S)-1) ret.eb(rev[lca(S[i],S[i+1])],S[i+1]);
		return ret;
	}
};

const int mx = 500005;

LCA<mx> tr;
int N;
ll bound;
bool isY[mx];
ll highest[mx][2];
int typ[mx];

void Init(int _N, int A[], int B[], int D[]) {
	N = _N;
	for(int i = 0; i <= N-2; i++){
		int a = A[i];
		int b = B[i];
		a++;
		b++;
		ll d = D[i];
		tr.ae(a, b, d);
	}
	tr.init(N+2);
	bound = ll(N)*ll(log2(N)*0.5);
	for(int i = 1; i <= N; i++){
		typ[i] = 2;
		highest[i][0] = INF;
		highest[i][1] = INF;
	}
	//bound = 0;
	/*for(int i = 1; i <= N; i++){
		ps(i, tr.dist[i]);
	}*/
}

ll ans;
vi children[mx];


void search(int node){
	for(auto u: children[node]){
		search(u);
		for(int j = 0; j < 2; j++){
			ckmin(highest[node][j], highest[u][j]);
		}
	}
	if(typ[node] != 2){
		int t = typ[node];
		ckmin(highest[node][t], tr.getDist(node, 1));
	}
}

long long Query(int S, int X[], int T, int Y[]) {

	for(int i = 0; i < S; i++) X[i]++;
	for(int i = 0; i < T; i++) Y[i]++;
	vi nodes;
	for(int i = 0; i < S; i++){
		nodes.pb(X[i]);
		typ[X[i]] = 0;
	}
	for(int i = 0; i < T; i++){
		nodes.pb(Y[i]);
		typ[Y[i]] = 1;
	}

	vpi par = tr.compress(nodes);
	/*for(int i = 1; i <= N; i++){
		ps(i, tr.dist[i]);
	}
	ps("nodes", nodes);
	ps("par", par);*/
	for(auto u: par){
		if(par[u.f].s == u.s) continue;
		children[par[u.f].s].pb(u.s);
	}
	/*for(int i = 1; i <= N; i++){
		ps(i, children[i]);
	}*/
	search(par[0].s);
	ans = INF;
	for(auto x: par){
		int u = x.s;
		ckmin(ans, highest[u][0]+highest[u][1]-2*tr.getDist(1, u));
	}
	//reset arrays based on nodes
	for(auto x: par){
		int u = x.s;
		typ[u] = 2;
		children[u].clear();
		highest[u][0] = highest[u][1] = INF;
	}
	return ans;
}


/*int main() {
	setIO();
	
	// you should actually read the stuff at the bottom
}*/

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

Compilation message

factories.cpp: In function 'void setIn(std::__cxx11::string)':
factories.cpp:124:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void setOut(std::__cxx11::string)':
factories.cpp:125:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 24448 KB Output is correct
2 Correct 918 ms 42744 KB Output is correct
3 Correct 961 ms 42744 KB Output is correct
4 Correct 950 ms 42844 KB Output is correct
5 Correct 869 ms 42872 KB Output is correct
6 Correct 613 ms 42680 KB Output is correct
7 Correct 946 ms 42744 KB Output is correct
8 Correct 935 ms 42928 KB Output is correct
9 Correct 868 ms 43000 KB Output is correct
10 Correct 619 ms 42600 KB Output is correct
11 Correct 954 ms 42596 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24064 KB Output is correct
2 Correct 1700 ms 173092 KB Output is correct
3 Correct 1726 ms 175532 KB Output is correct
4 Correct 1168 ms 170588 KB Output is correct
5 Correct 1723 ms 205904 KB Output is correct
6 Correct 1838 ms 176872 KB Output is correct
7 Correct 1489 ms 74468 KB Output is correct
8 Correct 989 ms 74092 KB Output is correct
9 Correct 1341 ms 80580 KB Output is correct
10 Correct 1632 ms 75880 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 24448 KB Output is correct
2 Correct 918 ms 42744 KB Output is correct
3 Correct 961 ms 42744 KB Output is correct
4 Correct 950 ms 42844 KB Output is correct
5 Correct 869 ms 42872 KB Output is correct
6 Correct 613 ms 42680 KB Output is correct
7 Correct 946 ms 42744 KB Output is correct
8 Correct 935 ms 42928 KB Output is correct
9 Correct 868 ms 43000 KB Output is correct
10 Correct 619 ms 42600 KB Output is correct
11 Correct 954 ms 42596 KB Output is correct
12 Correct 20 ms 24064 KB Output is correct
13 Correct 1700 ms 173092 KB Output is correct
14 Correct 1726 ms 175532 KB Output is correct
15 Correct 1168 ms 170588 KB Output is correct
16 Correct 1723 ms 205904 KB Output is correct
17 Correct 1838 ms 176872 KB Output is correct
18 Correct 1489 ms 74468 KB Output is correct
19 Correct 989 ms 74092 KB Output is correct
20 Correct 1341 ms 80580 KB Output is correct
21 Correct 1632 ms 75880 KB Output is correct
22 Correct 3014 ms 182352 KB Output is correct
23 Correct 2955 ms 183888 KB Output is correct
24 Correct 3635 ms 187164 KB Output is correct
25 Correct 3196 ms 189884 KB Output is correct
26 Correct 2877 ms 179508 KB Output is correct
27 Correct 3015 ms 209488 KB Output is correct
28 Correct 1915 ms 178476 KB Output is correct
29 Correct 2824 ms 178568 KB Output is correct
30 Correct 3033 ms 201416 KB Output is correct
31 Correct 2784 ms 201552 KB Output is correct
32 Correct 1519 ms 83328 KB Output is correct
33 Correct 971 ms 77064 KB Output is correct
34 Correct 1500 ms 73192 KB Output is correct
35 Correct 1540 ms 73188 KB Output is correct
36 Correct 1717 ms 73972 KB Output is correct
37 Correct 1707 ms 73732 KB Output is correct