oj.uz

Submission #333249

# Submission time Handle Problem Language Result Execution time Memory
333249 2020-12-05T04:48:19 Z aloo123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 204948 KB 
#include <bits/stdc++.h>
#include "factories.h"


using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using vl = vector<ll>; 
#define mp make_pair
#define f first
#define s second
 
// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define ins insert 
#define pf push_front 
#define pb push_back
 
// loops
#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 ll INF = 1e18; // not too close to LLONG_MAX

// #define int ll
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!!
const int MAXN = 1e6+5;
const int LOGN = 25;

ll n,current_tree = 0;
vector<pl> g[MAXN];
ll best[MAXN],deleted[MAXN];
ll depth[MAXN];
ll par[MAXN],sub[MAXN];
ll dist[LOGN][MAXN];
// initally all nodes are red

ll LCA(ll u,ll v){
	// finds LCA in of u and v in the centroid tree
	while(u != v){
		if(depth[u] < depth[v])
			v = par[v]; // get v a level up
		else
			u = par[u]; // get u a level up
	}
	return u;
}
ll compute_dist(ll x,ll y){
	ll lc = depth[LCA(x,y)];
	return dist[lc][x] + dist[lc][y];
}
void find_subtree(ll u,ll p){
	sub[u] = 1;
	current_tree++;
	trav(P,g[u]){
		int v = P.f;
		if(deleted[v] == 0 && v != p){
			find_subtree(v,u);
			sub[u] += sub[v];
		}
	}
}
ll find_centroid(ll u,ll p){
	trav(P,g[u]){
		ll v = P.f;
		if(deleted[v] == 0 && v !=p  && sub[v] > (current_tree / 2)) return find_centroid(v,u);
	}
	return u;
}
void dfs(ll u,ll p,ll lvl,ll dd){
	dist[lvl][u] = dd;
	trav(P,g[u]){
		ll v = P.f;
		ll w = P.s;
		if(deleted[v] == 0 && v != p){
			dfs(v,u,lvl,dd + w);
		}
	}
}
void decompose(ll root,ll p){
	current_tree = 0;
	find_subtree(root,p);
	ll cen = find_centroid(root,p);
	par[cen] = p;
	if(p != -1) depth[cen] = depth[p] + 1;
	dfs(cen,p,depth[cen],0);
	deleted[cen] = 1;
	trav(P,g[cen]){
		int v = P.f;
		if(deleted[v] == 1) continue;
		decompose(v,cen);
	}
}

ll query(ll u){
	// find the nearest blue node to u
	ll ans = best[u];
	ll x = u;
	u = par[u];
	while(u != -1){
		ans = min(ans,compute_dist(x,u) + best[u]);
		u = par[u];
    }
	return ans;
}
void update(ll u){
	// colour node u to blue
	ll x = u;
	while(u != -1){
		best[u] = min(best[u],compute_dist(u,x));
		u = par[u];
	}
}
void remove_col(ll u){
	// u has to be a blue node
	// remove its colour
	while(u != -1){
		best[u] = INF;
		u = par[u];
	}
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	FOR(i,0,n-1){A[i]++,B[i]++;
		g[A[i]].pb(mp(B[i],D[i]));
		g[B[i]].pb(mp(A[i],D[i]));
	}

	for(int i =1;i<=n;i++) best[i] = INF;
	decompose(1,-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]++;
    for(int i = 0;i < T;i++){
		update(Y[i]);
    }
    ll ans = INF;
	for(int i = 0;i< S;i++){
		ans = min(ans,query(X[i]));
	}
	for(int i =0;i<T;i++){
		remove_col(Y[i]);
	}
	return ans;
}

/* void solve(){
	cin >> n;
	int q;
	cin >> q;
	FOR(i,2,n+1){
		int u,v,w;
		cin >> u >> v >> w;
		u++,v++;
		g[u].pb(mp(v,w));
		g[v].pb(mp(u,w));	
	}
	for(int i =1;i<=n;i++) best[i] = INF;
	decompose(1,-1);
	FOR(i,1,n+1){
		cout << i << " " << par[i] << endl;
	}
	while(q--){
		int s,t;
		cin >> s >> t;
		vl u(s),v(t);
		for(int i =0;i<s;i++) cin >> u[i],u[i]++;
		for(int i =0;i<t;i++) cin >> v[i],v[i]++;
		for(int i = 0;i < t;i++){
			update(v[i]);
		}
		int ans = INF;
		for(int i = 0;i< s;i++){
			ans = min(ans,query(u[i]));
		}
		cout << ans << endl;
		for(int i =0;i<t;i++){
			remove_col(v[i]);
		}
	}
}	
signed main() {
	cin.tie(0)->sync_with_stdio(0);

	// you should actually read the stuff at the bottom
	int t=1;
	// cin >> t;
	while(t--){
		solve();
	}
} */
/* stuff you should look for
	* read the probem 3 more times in case of WA :)
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24300 KB Output is correct
2 Correct 433 ms 33004 KB Output is correct
3 Correct 521 ms 42604 KB Output is correct
4 Correct 525 ms 42476 KB Output is correct
5 Correct 623 ms 42988 KB Output is correct
6 Correct 310 ms 42092 KB Output is correct
7 Correct 526 ms 42604 KB Output is correct
8 Correct 542 ms 42476 KB Output is correct
9 Correct 628 ms 42732 KB Output is correct
10 Correct 306 ms 42092 KB Output is correct
11 Correct 535 ms 42476 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24044 KB Output is correct
2 Correct 3053 ms 141156 KB Output is correct
3 Correct 4817 ms 177380 KB Output is correct
4 Correct 880 ms 105928 KB Output is correct
5 Correct 6434 ms 202836 KB Output is correct
6 Correct 5011 ms 179420 KB Output is correct
7 Correct 2608 ms 71276 KB Output is correct
8 Correct 479 ms 59484 KB Output is correct
9 Correct 3147 ms 75500 KB Output is correct
10 Correct 2592 ms 72812 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24300 KB Output is correct
2 Correct 433 ms 33004 KB Output is correct
3 Correct 521 ms 42604 KB Output is correct
4 Correct 525 ms 42476 KB Output is correct
5 Correct 623 ms 42988 KB Output is correct
6 Correct 310 ms 42092 KB Output is correct
7 Correct 526 ms 42604 KB Output is correct
8 Correct 542 ms 42476 KB Output is correct
9 Correct 628 ms 42732 KB Output is correct
10 Correct 306 ms 42092 KB Output is correct
11 Correct 535 ms 42476 KB Output is correct
12 Correct 18 ms 24044 KB Output is correct
13 Correct 3053 ms 141156 KB Output is correct
14 Correct 4817 ms 177380 KB Output is correct
15 Correct 880 ms 105928 KB Output is correct
16 Correct 6434 ms 202836 KB Output is correct
17 Correct 5011 ms 179420 KB Output is correct
18 Correct 2608 ms 71276 KB Output is correct
19 Correct 479 ms 59484 KB Output is correct
20 Correct 3147 ms 75500 KB Output is correct
21 Correct 2592 ms 72812 KB Output is correct
22 Correct 4223 ms 165868 KB Output is correct
23 Correct 4200 ms 170636 KB Output is correct
24 Correct 6902 ms 185708 KB Output is correct
25 Correct 6867 ms 189408 KB Output is correct
26 Correct 6931 ms 185832 KB Output is correct
27 Execution timed out 8106 ms 204948 KB Time limit exceeded
28 Halted 0 ms 0 KB -