oj.uz

Submission #296708

# Submission time Handle Problem Language Result Execution time Memory
296708 2020-09-10T20:11:30 Z b00n0rp Factories (JOI14_factories) C++17
15 / 100
 8000 ms 118580 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];

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() <= 5);
	// REP(i,n) cout << i << " " << cenpar[i] << endl;
}

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,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 24448 KB Output is correct
2 Correct 1128 ms 33072 KB Output is correct
3 Correct 2048 ms 33528 KB Output is correct
4 Correct 2072 ms 33528 KB Output is correct
5 Correct 2424 ms 33428 KB Output is correct
6 Correct 432 ms 33144 KB Output is correct
7 Correct 2032 ms 33400 KB Output is correct
8 Correct 2121 ms 33388 KB Output is correct
9 Correct 2418 ms 33612 KB Output is correct
10 Correct 441 ms 33272 KB Output is correct
11 Correct 2036 ms 33272 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24064 KB Output is correct
2 Correct 3763 ms 117496 KB Output is correct
3 Execution timed out 8053 ms 118580 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 24448 KB Output is correct
2 Correct 1128 ms 33072 KB Output is correct
3 Correct 2048 ms 33528 KB Output is correct
4 Correct 2072 ms 33528 KB Output is correct
5 Correct 2424 ms 33428 KB Output is correct
6 Correct 432 ms 33144 KB Output is correct
7 Correct 2032 ms 33400 KB Output is correct
8 Correct 2121 ms 33388 KB Output is correct
9 Correct 2418 ms 33612 KB Output is correct
10 Correct 441 ms 33272 KB Output is correct
11 Correct 2036 ms 33272 KB Output is correct
12 Correct 20 ms 24064 KB Output is correct
13 Correct 3763 ms 117496 KB Output is correct
14 Execution timed out 8053 ms 118580 KB Time limit exceeded
15 Halted 0 ms 0 KB -