oj.uz

Submission #333268

# Submission time Handle Problem Language Result Execution time Memory
333268 2020-12-05T05:53:37 Z aloo123 Factories (JOI14_factories) C++14
100 / 100
 6859 ms 203288 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,dist[depth[u]][x] + 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],dist[depth[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]++;
    int flip_a_coin = rand()%2;
    if(flip_a_coin){
        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 23 ms 24300 KB Output is correct
2 Correct 367 ms 33132 KB Output is correct
3 Correct 402 ms 33260 KB Output is correct
4 Correct 405 ms 33264 KB Output is correct
5 Correct 436 ms 33516 KB Output is correct
6 Correct 283 ms 32748 KB Output is correct
7 Correct 402 ms 33260 KB Output is correct
8 Correct 402 ms 33260 KB Output is correct
9 Correct 434 ms 33516 KB Output is correct
10 Correct 280 ms 32748 KB Output is correct
11 Correct 399 ms 33272 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24172 KB Output is correct
2 Correct 2801 ms 159980 KB Output is correct
3 Correct 4206 ms 177004 KB Output is correct
4 Correct 997 ms 107188 KB Output is correct
5 Correct 5464 ms 202288 KB Output is correct
6 Correct 4314 ms 178284 KB Output is correct
7 Correct 1486 ms 61036 KB Output is correct
8 Correct 459 ms 49500 KB Output is correct
9 Correct 1738 ms 64876 KB Output is correct
10 Correct 1496 ms 62188 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24300 KB Output is correct
2 Correct 367 ms 33132 KB Output is correct
3 Correct 402 ms 33260 KB Output is correct
4 Correct 405 ms 33264 KB Output is correct
5 Correct 436 ms 33516 KB Output is correct
6 Correct 283 ms 32748 KB Output is correct
7 Correct 402 ms 33260 KB Output is correct
8 Correct 402 ms 33260 KB Output is correct
9 Correct 434 ms 33516 KB Output is correct
10 Correct 280 ms 32748 KB Output is correct
11 Correct 399 ms 33272 KB Output is correct
12 Correct 16 ms 24172 KB Output is correct
13 Correct 2801 ms 159980 KB Output is correct
14 Correct 4206 ms 177004 KB Output is correct
15 Correct 997 ms 107188 KB Output is correct
16 Correct 5464 ms 202288 KB Output is correct
17 Correct 4314 ms 178284 KB Output is correct
18 Correct 1486 ms 61036 KB Output is correct
19 Correct 459 ms 49500 KB Output is correct
20 Correct 1738 ms 64876 KB Output is correct
21 Correct 1496 ms 62188 KB Output is correct
22 Correct 3571 ms 160716 KB Output is correct
23 Correct 3649 ms 164820 KB Output is correct
24 Correct 5699 ms 179052 KB Output is correct
25 Correct 5592 ms 182664 KB Output is correct
26 Correct 5580 ms 178924 KB Output is correct
27 Correct 6859 ms 200044 KB Output is correct
28 Correct 1217 ms 135624 KB Output is correct
29 Correct 5429 ms 203288 KB Output is correct
30 Correct 5407 ms 202468 KB Output is correct
31 Correct 5432 ms 203284 KB Output is correct
32 Correct 1765 ms 79852 KB Output is correct
33 Correct 466 ms 63836 KB Output is correct
34 Correct 998 ms 70124 KB Output is correct
35 Correct 1014 ms 70316 KB Output is correct
36 Correct 1412 ms 73068 KB Output is correct
37 Correct 1420 ms 73196 KB Output is correct