oj.uz

Submission #333253

# Submission time Handle Problem Language Result Execution time Memory
333253 2020-12-05T05:08:14 Z aloo123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 225756 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 = 5e5+5;
const int LOGN = 25;
const int LOGLOGN = 5;
ll n,current_tree = 0;
vector<pl> g[MAXN];
vector<ll> ct[MAXN];
ll best[MAXN],deleted[MAXN];
ll depth[MAXN];
ll par[MAXN],sub[MAXN];
ll dist[LOGN][MAXN];
ll r;
// initally all nodes are red
ll up[MAXN][LOGLOGN];
int tin[MAXN],tout[MAXN];
int timer = 0;
void dfs2(int u,int p){
    tin[u] = ++timer;
    if(p != -1){
        up[u][0] = p;
    }
    trav(v,ct[u]){
        if(v != p){
            dfs2(v,u);
        }
    }
    tout[u] = ++timer;
}
bool is_ans(int u,int v){
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
ll LCA(ll u,ll v){
	// finds LCA in of u and v in the centroid tree
	if(is_ans(u,v)) return u;
    if(is_ans(v,u)) return v;
    ROF(i,0,LOGLOGN){
        if(!is_ans(up[u][i],v)) 
            u = up[u][i];
    }
    return up[u][0];
}
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) r = cen;
	if(p != -1) depth[cen] = depth[p] + 1;
	if(p != -1){
        ct[p].pb(cen);
        ct[cen].pb(p);
    }
    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);
    dfs2(r,-1);
    FOR(i,1,LOGLOGN){
        FOR(j,1,n+1){
            if(up[j][i-1] != 0){
                up[j][i] = up[up[j][i-1]][i-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 430 ms 33260 KB Output is correct
3 Correct 477 ms 33388 KB Output is correct
4 Correct 486 ms 33516 KB Output is correct
5 Correct 533 ms 33644 KB Output is correct
6 Correct 306 ms 33004 KB Output is correct
7 Correct 477 ms 33524 KB Output is correct
8 Correct 488 ms 33772 KB Output is correct
9 Correct 540 ms 33772 KB Output is correct
10 Correct 304 ms 33004 KB Output is correct
11 Correct 475 ms 33388 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24172 KB Output is correct
2 Correct 3335 ms 183728 KB Output is correct
3 Correct 4929 ms 200600 KB Output is correct
4 Correct 1133 ms 130504 KB Output is correct
5 Correct 6425 ms 225756 KB Output is correct
6 Correct 5077 ms 201984 KB Output is correct
7 Correct 2311 ms 65936 KB Output is correct
8 Correct 559 ms 54236 KB Output is correct
9 Correct 2733 ms 69740 KB Output is correct
10 Correct 2310 ms 67356 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 430 ms 33260 KB Output is correct
3 Correct 477 ms 33388 KB Output is correct
4 Correct 486 ms 33516 KB Output is correct
5 Correct 533 ms 33644 KB Output is correct
6 Correct 306 ms 33004 KB Output is correct
7 Correct 477 ms 33524 KB Output is correct
8 Correct 488 ms 33772 KB Output is correct
9 Correct 540 ms 33772 KB Output is correct
10 Correct 304 ms 33004 KB Output is correct
11 Correct 475 ms 33388 KB Output is correct
12 Correct 18 ms 24172 KB Output is correct
13 Correct 3335 ms 183728 KB Output is correct
14 Correct 4929 ms 200600 KB Output is correct
15 Correct 1133 ms 130504 KB Output is correct
16 Correct 6425 ms 225756 KB Output is correct
17 Correct 5077 ms 201984 KB Output is correct
18 Correct 2311 ms 65936 KB Output is correct
19 Correct 559 ms 54236 KB Output is correct
20 Correct 2733 ms 69740 KB Output is correct
21 Correct 2310 ms 67356 KB Output is correct
22 Correct 4451 ms 184124 KB Output is correct
23 Correct 4432 ms 188504 KB Output is correct
24 Correct 6824 ms 202636 KB Output is correct
25 Correct 6809 ms 206064 KB Output is correct
26 Correct 6869 ms 202704 KB Output is correct
27 Execution timed out 8048 ms 222180 KB Time limit exceeded
28 Halted 0 ms 0 KB -