oj.uz

답안 #383942

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
383942 2021-03-31T04:33:57 Z wind_reaper 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 117944 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

const int N = 500000;
const int LOG = 20;
const int64_t INF = 1e18;

vector<array<int, 2>> g[N];

struct LCA{
	int tin[N], tout[N], up[LOG][N];
	int64_t depth[N];
	int timer = 0;

	void init(){
		dfs();
	}

	void dfs(int node = 0, int par = 0, int d = 0){
		depth[node] = depth[par] + int64_t(d);
		tin[node] = timer++;

		up[0][node] = par;
		for(int i = 1; i < LOG; i++)
			up[i][node] = up[i-1][up[i-1][node]];

		for(auto& [v, dx] : g[node]){
			if(v == par)
				continue;
			dfs(v, node, dx);
		}

		tout[node] = timer;
	}

	bool isAncestor(int u, int v){
		return tin[u] <= tin[v] && tout[u] >= tout[v];
	}

	int lca(int u, int v){
		if(isAncestor(u, v))
			return u;
		if(isAncestor(v, u))
			return v;

		for(int i = LOG-1; i >= 0; --i)
			if(!isAncestor(up[i][u], v))
				u = up[i][u];

		return up[0][u];
	}

	int64_t dist(int u, int v){
		return depth[u] + depth[v] - 2*depth[lca(u, v)];
	}
};

struct CentroidDecomposition{
	bool vis[N];
	vector<int> hit;
	int sz[N], par[N];
	int64_t best[N];

	LCA S;

	void init(int s, int A[], int B[], int D[]){
		memset(sz, 0, sizeof sz);
		memset(par, 0, sizeof par);
		
		for(int i = 0; i < s; i++)
			best[i] = INF;

		for(int i = 0; i < s-1; i++){
			g[A[i]].push_back({B[i], D[i]});
			g[B[i]].push_back({A[i], D[i]});
		}

		S.init();
		tree();
	}

	int find(int node, int p = -1){
		if(vis[node]) return 0;
		sz[node] = 1;
		for(auto& [v, d] : g[node]){
			if(v != p)
				sz[node] += find(v, node);
		}
		return sz[node];
	}

	int centroid(int node, int p, int n){
		for(auto& [v, d] : g[node]){
			if(v == p)
				continue;
			if(!vis[v] && sz[v] > n / 2)
				return centroid(v, node, n);
		}

		return node;
	}

	void tree(int node = 0, int p = -1){
		find(node);

		int c = centroid(node, -1, sz[node]);
		vis[c] = true;
		par[c] = p;

		for(auto& [v, d] : g[c]){
			if(!vis[v])
				tree(v, c);
		}
	}

	void update(int node){
		int u = node;
		while(u != -1){
			best[u] = min(best[u], S.dist(u, node));
			hit.push_back(u);
			u = par[u];
		}
	}

	int64_t query(int node){
		int64_t ans = INF;
		int u = node;
		while(u != -1){
			ans = min(ans, best[u] + S.dist(u, node));
			u = par[u];
		}
		return ans;
	}

	void reset(){
		for(int i : hit)
			best[i] = INF;
		hit.clear();
	}
}D;

void Init(int n, int A[], int B[], int d[]){
	D.init(n, A, B, d);
}

long long Query(int S, int X[], int T, int Y[]){
	for(int i = 0; i < S; i++)
		D.update(X[i]);
	int64_t ans = INF;
	for(int i = 0; i < T; i++)
		ans = min(ans, D.query(Y[i]));
	D.reset();
	return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 16748 KB Output is correct
2 Correct 884 ms 25580 KB Output is correct
3 Correct 1798 ms 34704 KB Output is correct
4 Correct 1803 ms 34832 KB Output is correct
5 Correct 717 ms 34924 KB Output is correct
6 Correct 271 ms 34668 KB Output is correct
7 Correct 1816 ms 34672 KB Output is correct
8 Correct 1922 ms 34604 KB Output is correct
9 Correct 718 ms 34924 KB Output is correct
10 Correct 276 ms 34412 KB Output is correct
11 Correct 1776 ms 34796 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 16364 KB Output is correct
2 Correct 5031 ms 98960 KB Output is correct
3 Execution timed out 8034 ms 117944 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 16748 KB Output is correct
2 Correct 884 ms 25580 KB Output is correct
3 Correct 1798 ms 34704 KB Output is correct
4 Correct 1803 ms 34832 KB Output is correct
5 Correct 717 ms 34924 KB Output is correct
6 Correct 271 ms 34668 KB Output is correct
7 Correct 1816 ms 34672 KB Output is correct
8 Correct 1922 ms 34604 KB Output is correct
9 Correct 718 ms 34924 KB Output is correct
10 Correct 276 ms 34412 KB Output is correct
11 Correct 1776 ms 34796 KB Output is correct
12 Correct 12 ms 16364 KB Output is correct
13 Correct 5031 ms 98960 KB Output is correct
14 Execution timed out 8034 ms 117944 KB Time limit exceeded
15 Halted 0 ms 0 KB -