oj.uz

Submission #333255

# Submission time Handle Problem Language Result Execution time Memory
333255 2020-12-05T05:13:59 Z aloo123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 225668 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]++;
    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 434 ms 33260 KB Output is correct
3 Correct 465 ms 36224 KB Output is correct
4 Correct 516 ms 36220 KB Output is correct
5 Correct 538 ms 36344 KB Output is correct
6 Correct 291 ms 35564 KB Output is correct
7 Correct 469 ms 36076 KB Output is correct
8 Correct 512 ms 36076 KB Output is correct
9 Correct 547 ms 36332 KB Output is correct
10 Correct 293 ms 35564 KB Output is correct
11 Correct 458 ms 36076 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 3332 ms 183708 KB Output is correct
3 Correct 4907 ms 200972 KB Output is correct
4 Correct 1092 ms 130612 KB Output is correct
5 Correct 6388 ms 225668 KB Output is correct
6 Correct 5138 ms 201884 KB Output is correct
7 Correct 2253 ms 66624 KB Output is correct
8 Correct 521 ms 55004 KB Output is correct
9 Correct 2732 ms 70508 KB Output is correct
10 Correct 2343 ms 67948 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 434 ms 33260 KB Output is correct
3 Correct 465 ms 36224 KB Output is correct
4 Correct 516 ms 36220 KB Output is correct
5 Correct 538 ms 36344 KB Output is correct
6 Correct 291 ms 35564 KB Output is correct
7 Correct 469 ms 36076 KB Output is correct
8 Correct 512 ms 36076 KB Output is correct
9 Correct 547 ms 36332 KB Output is correct
10 Correct 293 ms 35564 KB Output is correct
11 Correct 458 ms 36076 KB Output is correct
12 Correct 18 ms 24172 KB Output is correct
13 Correct 3332 ms 183708 KB Output is correct
14 Correct 4907 ms 200972 KB Output is correct
15 Correct 1092 ms 130612 KB Output is correct
16 Correct 6388 ms 225668 KB Output is correct
17 Correct 5138 ms 201884 KB Output is correct
18 Correct 2253 ms 66624 KB Output is correct
19 Correct 521 ms 55004 KB Output is correct
20 Correct 2732 ms 70508 KB Output is correct
21 Correct 2343 ms 67948 KB Output is correct
22 Correct 4588 ms 184096 KB Output is correct
23 Correct 4794 ms 188540 KB Output is correct
24 Correct 7102 ms 202500 KB Output is correct
25 Correct 7261 ms 205960 KB Output is correct
26 Correct 6876 ms 202512 KB Output is correct
27 Execution timed out 8055 ms 221936 KB Time limit exceeded
28 Halted 0 ms 0 KB -