oj.uz

Submission #296729

# Submission time Handle Problem Language Result Execution time Memory
296729 2020-09-10T20:30:02 Z b00n0rp Factories (JOI14_factories) C++17
15 / 100
 8000 ms 224692 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() <= 6);
	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 24 ms 24320 KB Output is correct
2 Correct 379 ms 33656 KB Output is correct
3 Correct 408 ms 33504 KB Output is correct
4 Correct 413 ms 33656 KB Output is correct
5 Correct 419 ms 33784 KB Output is correct
6 Correct 298 ms 33528 KB Output is correct
7 Correct 402 ms 33528 KB Output is correct
8 Correct 406 ms 33656 KB Output is correct
9 Correct 421 ms 33784 KB Output is correct
10 Correct 297 ms 33540 KB Output is correct
11 Correct 401 ms 33528 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24272 KB Output is correct
2 Correct 2790 ms 199416 KB Output is correct
3 Correct 5728 ms 201400 KB Output is correct
4 Correct 962 ms 197128 KB Output is correct
5 Execution timed out 8115 ms 224692 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24320 KB Output is correct
2 Correct 379 ms 33656 KB Output is correct
3 Correct 408 ms 33504 KB Output is correct
4 Correct 413 ms 33656 KB Output is correct
5 Correct 419 ms 33784 KB Output is correct
6 Correct 298 ms 33528 KB Output is correct
7 Correct 402 ms 33528 KB Output is correct
8 Correct 406 ms 33656 KB Output is correct
9 Correct 421 ms 33784 KB Output is correct
10 Correct 297 ms 33540 KB Output is correct
11 Correct 401 ms 33528 KB Output is correct
12 Correct 18 ms 24272 KB Output is correct
13 Correct 2790 ms 199416 KB Output is correct
14 Correct 5728 ms 201400 KB Output is correct
15 Correct 962 ms 197128 KB Output is correct
16 Execution timed out 8115 ms 224692 KB Time limit exceeded
17 Halted 0 ms 0 KB -