oj.uz

답안 #296710

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
296710 2020-09-10T20:13:17 Z b00n0rp 공장들 (JOI14_factories) C++17
18 / 100
 8000 ms 161436 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;
	// 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,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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 24192 KB Output is correct
2 Execution timed out 8053 ms 32632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 24064 KB Output is correct
2 Correct 2447 ms 117544 KB Output is correct
3 Correct 5599 ms 119196 KB Output is correct
4 Correct 1331 ms 133244 KB Output is correct
5 Correct 5797 ms 161436 KB Output is correct
6 Correct 4578 ms 139308 KB Output is correct
7 Correct 6801 ms 64928 KB Output is correct
8 Correct 1482 ms 65128 KB Output is correct
9 Correct 6491 ms 69140 KB Output is correct
10 Correct 4189 ms 66188 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 24192 KB Output is correct
2 Execution timed out 8053 ms 32632 KB Time limit exceeded
3 Halted 0 ms 0 KB -