oj.uz

Submission #296707

# Submission time Handle Problem Language Result Execution time Memory
296707 2020-09-10T20:06:57 Z b00n0rp Factories (JOI14_factories) C++17
15 / 100
 8000 ms 136572 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pii pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define pb push_back

int n,centroid;
const int MAXN = 500005;
const ll INF = 1e16;

int par[MAXN][21],cenpar[MAXN];
int dep[MAXN],sz[MAXN];
vector<pii> adj[MAXN];
bitset<MAXN> vis;

vi g[MAXN];

ll mnd[MAXN],dist[MAXN];

void dfs0(int u){
	for(auto v:adj[u]){
		if(v.F != par[u][0]){
			par[v.F][0] = u;
			dep[v.F] = dep[u]+1;
			dist[v.F] = dist[u]+v.S;
			dfs0(v.F);
		}
	}
}

void dfs_sz(int u,int p){
	sz[u] = 1;
	for(auto v:adj[u]){
		if(v.F != p and vis[v.F] == 0){
			dfs_sz(v.F,u);
			sz[u] += sz[v.F];
		}
	}
}

int find_centroid(int u,int p,int tot){
	for(auto v:adj[u]){
		if(v.F == p or vis[v.F]) continue;
		if(sz[v.F] > tot/2) return find_centroid(v.F,u,tot); 
	}
	return u;
}

void centroid_decomposition(int u,int p){
	dfs_sz(u,u);
	int cen = find_centroid(u,p,sz[u]);
	if(p == -1) centroid = cen;
	else g[p].pb(cen);
	cenpar[cen] = p;
	vis[cen] = 1;
	for(auto v:adj[cen]){
		if(!vis[v.F]) centroid_decomposition(v.F,cen);
	}
}

int lca(int u,int v){
	if(dep[u] < dep[v]) swap(u,v);
	for(int i = 20; i >= 0; i --){
		if(dep[u]-(1<<i) >= dep[v]) u = par[u][i];
	}
	if(u == v) return u;
	for(int i = 20; i >= 0; i --){
		if(par[u][i] != par[v][i]){
			u = par[u][i];
			v = par[v][i];
		}
	}
	return par[u][0];
}

ll calc_dist(int u,int v){
	// cout << u << " " << v << " " << lca(u,v) << endl;
	return dist[u]+dist[v]-2*dist[lca(u,v)];
}

void Init(int N, int A[], int B[], int D[]){
	n = N;
	REP(i,n-1){
		adj[A[i]].pb({B[i],D[i]});
		adj[B[i]].pb({A[i],D[i]});
	}
	par[0][0] = 0;
	dep[0] = 0;
	dfs0(0);
	FOR(j,1,21){
		REP(i,n){
			par[i][j] = par[par[i][j-1]][j-1];
		}
	}
	centroid_decomposition(0,-1);
	REP(i,n+1) mnd[i] = INF;
}

void upd(int u,int type){
	int cur = u;
	while(cur != -1){
		if(type == 0){
			mnd[cur] = min(mnd[cur],calc_dist(cur,u));
		}
		else mnd[cur] = INF;
		cur = cenpar[cur];
	}
}

ll quer(int u){
	ll res = INF;
	int cur = u;
	while(cur != -1){
		res = min(res,calc_dist(u,cur)+mnd[cur]);
		cur = cenpar[cur];
	}
	return res;
}

ll Query(int S, int X[], int T, int Y[]) {
	REP(i,S) upd(X[i],0);
	ll ans = INF;
	// REP(i,S){
	// 	REP(j,T){
	// 		ans = min(ans,calc_dist(X[i],Y[j]));
	// 	}
	// }
	REP(i,T) ans = min(ans,quer(Y[i]));
	REP(i,S) upd(X[i],1);
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24312 KB Output is correct
2 Correct 1153 ms 42232 KB Output is correct
3 Correct 2071 ms 42360 KB Output is correct
4 Correct 2033 ms 42488 KB Output is correct
5 Correct 2472 ms 42488 KB Output is correct
6 Correct 453 ms 42360 KB Output is correct
7 Correct 2076 ms 42616 KB Output is correct
8 Correct 2199 ms 42336 KB Output is correct
9 Correct 2460 ms 42616 KB Output is correct
10 Correct 451 ms 42340 KB Output is correct
11 Correct 2050 ms 42488 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24056 KB Output is correct
2 Correct 3814 ms 136008 KB Output is correct
3 Execution timed out 8018 ms 136572 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24312 KB Output is correct
2 Correct 1153 ms 42232 KB Output is correct
3 Correct 2071 ms 42360 KB Output is correct
4 Correct 2033 ms 42488 KB Output is correct
5 Correct 2472 ms 42488 KB Output is correct
6 Correct 453 ms 42360 KB Output is correct
7 Correct 2076 ms 42616 KB Output is correct
8 Correct 2199 ms 42336 KB Output is correct
9 Correct 2460 ms 42616 KB Output is correct
10 Correct 451 ms 42340 KB Output is correct
11 Correct 2050 ms 42488 KB Output is correct
12 Correct 20 ms 24056 KB Output is correct
13 Correct 3814 ms 136008 KB Output is correct
14 Execution timed out 8018 ms 136572 KB Time limit exceeded
15 Halted 0 ms 0 KB -