oj.uz

Submission #333257

# Submission time Handle Problem Language Result Execution time Memory
333257 2020-12-05T05:16:57 Z aloo123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 221440 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 = 4;
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]++;
    if(S<T){
        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;
    }
    else{
        for(int i = 0;i < S;i++){
            update(X[i]);
        }
        ll ans = INF;
        for(int i = 0;i< T;i++){
            ans = min(ans,query(Y[i]));
        }
        for(int i =0;i<S;i++){
            remove_col(X[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 424 ms 33436 KB Output is correct
3 Correct 485 ms 33388 KB Output is correct
4 Correct 560 ms 33364 KB Output is correct
5 Correct 535 ms 33644 KB Output is correct
6 Correct 289 ms 33004 KB Output is correct
7 Correct 459 ms 33388 KB Output is correct
8 Correct 520 ms 33564 KB Output is correct
9 Correct 543 ms 33772 KB Output is correct
10 Correct 285 ms 32876 KB Output is correct
11 Correct 478 ms 33516 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 3344 ms 179752 KB Output is correct
3 Correct 4917 ms 196460 KB Output is correct
4 Correct 1097 ms 126536 KB Output is correct
5 Correct 6406 ms 221440 KB Output is correct
6 Correct 5081 ms 197964 KB Output is correct
7 Correct 2270 ms 65356 KB Output is correct
8 Correct 530 ms 53596 KB Output is correct
9 Correct 2759 ms 68844 KB Output is correct
10 Correct 2346 ms 66424 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 424 ms 33436 KB Output is correct
3 Correct 485 ms 33388 KB Output is correct
4 Correct 560 ms 33364 KB Output is correct
5 Correct 535 ms 33644 KB Output is correct
6 Correct 289 ms 33004 KB Output is correct
7 Correct 459 ms 33388 KB Output is correct
8 Correct 520 ms 33564 KB Output is correct
9 Correct 543 ms 33772 KB Output is correct
10 Correct 285 ms 32876 KB Output is correct
11 Correct 478 ms 33516 KB Output is correct
12 Correct 18 ms 24172 KB Output is correct
13 Correct 3344 ms 179752 KB Output is correct
14 Correct 4917 ms 196460 KB Output is correct
15 Correct 1097 ms 126536 KB Output is correct
16 Correct 6406 ms 221440 KB Output is correct
17 Correct 5081 ms 197964 KB Output is correct
18 Correct 2270 ms 65356 KB Output is correct
19 Correct 530 ms 53596 KB Output is correct
20 Correct 2759 ms 68844 KB Output is correct
21 Correct 2346 ms 66424 KB Output is correct
22 Correct 4609 ms 180076 KB Output is correct
23 Correct 4764 ms 184508 KB Output is correct
24 Correct 7024 ms 198404 KB Output is correct
25 Correct 6950 ms 201744 KB Output is correct
26 Correct 6863 ms 198648 KB Output is correct
27 Execution timed out 8108 ms 217928 KB Time limit exceeded
28 Halted 0 ms 0 KB -