oj.uz

Submission #296725

# Submission time Handle Problem Language Result Execution time Memory
296725 2020-09-10T20:29:15 Z b00n0rp Factories (JOI14_factories) C++17
15 / 100
 7443 ms 450808 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
#define runtime() ((double)(clock())/CLOCKS_PER_SEC)

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];
ll cendist[MAXN][21];

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){
	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;
	REP(i,n){
		int cur = i,cnt = 0;
		while(cur != -1){
			cendist[i][cnt] = calc_dist(i,cur);
			cnt++;
			cur = cenpar[cur];
		}
	}
	assert(runtime() <= 6);
}

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

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

ll Query(int S, int X[], int T, int Y[]) {
	REP(i,S) upd(X[i],0);
	ll ans = INF;
	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 25 ms 24448 KB Output is correct
2 Correct 419 ms 34936 KB Output is correct
3 Correct 438 ms 34680 KB Output is correct
4 Correct 446 ms 34808 KB Output is correct
5 Correct 466 ms 35064 KB Output is correct
6 Correct 340 ms 34808 KB Output is correct
7 Correct 437 ms 34808 KB Output is correct
8 Correct 449 ms 34808 KB Output is correct
9 Correct 462 ms 35064 KB Output is correct
10 Correct 334 ms 34680 KB Output is correct
11 Correct 448 ms 34936 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24192 KB Output is correct
2 Correct 2940 ms 199412 KB Output is correct
3 Correct 6053 ms 201232 KB Output is correct
4 Correct 1014 ms 197212 KB Output is correct
5 Runtime error 7443 ms 450808 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24448 KB Output is correct
2 Correct 419 ms 34936 KB Output is correct
3 Correct 438 ms 34680 KB Output is correct
4 Correct 446 ms 34808 KB Output is correct
5 Correct 466 ms 35064 KB Output is correct
6 Correct 340 ms 34808 KB Output is correct
7 Correct 437 ms 34808 KB Output is correct
8 Correct 449 ms 34808 KB Output is correct
9 Correct 462 ms 35064 KB Output is correct
10 Correct 334 ms 34680 KB Output is correct
11 Correct 448 ms 34936 KB Output is correct
12 Correct 21 ms 24192 KB Output is correct
13 Correct 2940 ms 199412 KB Output is correct
14 Correct 6053 ms 201232 KB Output is correct
15 Correct 1014 ms 197212 KB Output is correct
16 Runtime error 7443 ms 450808 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -