oj.uz

Submission #296730

# Submission time Handle Problem Language Result Execution time Memory
296730 2020-09-10T20:30:23 Z b00n0rp Factories (JOI14_factories) C++17
15 / 100
 2797 ms 238876 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;
	assert(runtime() <= 2);
	REP(i,n){
		int cur = i,cnt = 0;
		while(cur != -1){
			cendist[i][cnt] = calc_dist(i,cur);
			cnt++;
			cur = cenpar[cur];
		}
	}
}

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 24320 KB Output is correct
2 Correct 378 ms 33528 KB Output is correct
3 Correct 458 ms 33708 KB Output is correct
4 Correct 399 ms 33528 KB Output is correct
5 Correct 432 ms 33784 KB Output is correct
6 Correct 301 ms 33528 KB Output is correct
7 Correct 424 ms 33528 KB Output is correct
8 Correct 438 ms 33564 KB Output is correct
9 Correct 465 ms 33780 KB Output is correct
10 Correct 312 ms 33528 KB Output is correct
11 Correct 402 ms 33528 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24192 KB Output is correct
2 Correct 2797 ms 199480 KB Output is correct
3 Runtime error 2221 ms 238876 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24320 KB Output is correct
2 Correct 378 ms 33528 KB Output is correct
3 Correct 458 ms 33708 KB Output is correct
4 Correct 399 ms 33528 KB Output is correct
5 Correct 432 ms 33784 KB Output is correct
6 Correct 301 ms 33528 KB Output is correct
7 Correct 424 ms 33528 KB Output is correct
8 Correct 438 ms 33564 KB Output is correct
9 Correct 465 ms 33780 KB Output is correct
10 Correct 312 ms 33528 KB Output is correct
11 Correct 402 ms 33528 KB Output is correct
12 Correct 18 ms 24192 KB Output is correct
13 Correct 2797 ms 199480 KB Output is correct
14 Runtime error 2221 ms 238876 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -