oj.uz

Submission #333250

# Submission time Handle Problem Language Result Execution time Memory
333250 2020-12-05T05:03:54 Z aloo123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 303800 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;

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][LOGN];
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,MAXN){
        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,LOGN){
        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 27 ms 24556 KB Output is correct
2 Correct 408 ms 34156 KB Output is correct
3 Correct 473 ms 35820 KB Output is correct
4 Correct 461 ms 35852 KB Output is correct
5 Correct 514 ms 36132 KB Output is correct
6 Correct 287 ms 35180 KB Output is correct
7 Correct 461 ms 35692 KB Output is correct
8 Correct 498 ms 35692 KB Output is correct
9 Correct 515 ms 36076 KB Output is correct
10 Correct 291 ms 35308 KB Output is correct
11 Correct 466 ms 35840 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24300 KB Output is correct
2 Correct 3454 ms 261904 KB Output is correct
3 Correct 5060 ms 278924 KB Output is correct
4 Correct 1249 ms 208816 KB Output is correct
5 Correct 6506 ms 303800 KB Output is correct
6 Correct 5217 ms 280100 KB Output is correct
7 Correct 2302 ms 82924 KB Output is correct
8 Correct 549 ms 71388 KB Output is correct
9 Correct 2696 ms 87020 KB Output is correct
10 Correct 2329 ms 84204 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24556 KB Output is correct
2 Correct 408 ms 34156 KB Output is correct
3 Correct 473 ms 35820 KB Output is correct
4 Correct 461 ms 35852 KB Output is correct
5 Correct 514 ms 36132 KB Output is correct
6 Correct 287 ms 35180 KB Output is correct
7 Correct 461 ms 35692 KB Output is correct
8 Correct 498 ms 35692 KB Output is correct
9 Correct 515 ms 36076 KB Output is correct
10 Correct 291 ms 35308 KB Output is correct
11 Correct 466 ms 35840 KB Output is correct
12 Correct 18 ms 24300 KB Output is correct
13 Correct 3454 ms 261904 KB Output is correct
14 Correct 5060 ms 278924 KB Output is correct
15 Correct 1249 ms 208816 KB Output is correct
16 Correct 6506 ms 303800 KB Output is correct
17 Correct 5217 ms 280100 KB Output is correct
18 Correct 2302 ms 82924 KB Output is correct
19 Correct 549 ms 71388 KB Output is correct
20 Correct 2696 ms 87020 KB Output is correct
21 Correct 2329 ms 84204 KB Output is correct
22 Correct 4558 ms 262252 KB Output is correct
23 Correct 4616 ms 266604 KB Output is correct
24 Correct 6887 ms 280556 KB Output is correct
25 Correct 6882 ms 284076 KB Output is correct
26 Correct 7063 ms 281132 KB Output is correct
27 Execution timed out 8048 ms 300248 KB Time limit exceeded
28 Halted 0 ms 0 KB -