oj.uz

Submission #333258

# Submission time Handle Problem Language Result Execution time Memory
333258 2020-12-05T05:19:24 Z aloo123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 221804 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]++;
    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 24 ms 24300 KB Output is correct
2 Correct 412 ms 33264 KB Output is correct
3 Correct 466 ms 33388 KB Output is correct
4 Correct 463 ms 33388 KB Output is correct
5 Correct 527 ms 33644 KB Output is correct
6 Correct 295 ms 32876 KB Output is correct
7 Correct 463 ms 33388 KB Output is correct
8 Correct 479 ms 33452 KB Output is correct
9 Correct 517 ms 33772 KB Output is correct
10 Correct 287 ms 32876 KB Output is correct
11 Correct 463 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 3317 ms 179636 KB Output is correct
3 Correct 4912 ms 196656 KB Output is correct
4 Correct 1086 ms 126672 KB Output is correct
5 Correct 6351 ms 221804 KB Output is correct
6 Correct 5100 ms 197912 KB Output is correct
7 Correct 2311 ms 65004 KB Output is correct
8 Correct 521 ms 53468 KB Output is correct
9 Correct 2665 ms 68968 KB Output is correct
10 Correct 2319 ms 66200 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24300 KB Output is correct
2 Correct 412 ms 33264 KB Output is correct
3 Correct 466 ms 33388 KB Output is correct
4 Correct 463 ms 33388 KB Output is correct
5 Correct 527 ms 33644 KB Output is correct
6 Correct 295 ms 32876 KB Output is correct
7 Correct 463 ms 33388 KB Output is correct
8 Correct 479 ms 33452 KB Output is correct
9 Correct 517 ms 33772 KB Output is correct
10 Correct 287 ms 32876 KB Output is correct
11 Correct 463 ms 33388 KB Output is correct
12 Correct 18 ms 24172 KB Output is correct
13 Correct 3317 ms 179636 KB Output is correct
14 Correct 4912 ms 196656 KB Output is correct
15 Correct 1086 ms 126672 KB Output is correct
16 Correct 6351 ms 221804 KB Output is correct
17 Correct 5100 ms 197912 KB Output is correct
18 Correct 2311 ms 65004 KB Output is correct
19 Correct 521 ms 53468 KB Output is correct
20 Correct 2665 ms 68968 KB Output is correct
21 Correct 2319 ms 66200 KB Output is correct
22 Correct 4339 ms 180100 KB Output is correct
23 Correct 4470 ms 184708 KB Output is correct
24 Correct 6803 ms 198612 KB Output is correct
25 Correct 6686 ms 201912 KB Output is correct
26 Correct 6874 ms 198700 KB Output is correct
27 Execution timed out 8103 ms 218180 KB Time limit exceeded
28 Halted 0 ms 0 KB -