답안 #890117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890117 2023-12-20T14:53:03 Z Onown 공장들 (JOI14_factories) C++17
33 / 100
8000 ms 204668 KB
#include <bits/stdc++.h>
#include <factories.h>
#pragma  GCC optimize ("Ofast")
using namespace std;
 
const int N = 5e5 + 55, L = 2e0 + 20, Q = 185;
const long long I = 1e18 + 118;
int n, q, h[N], par[N][L];
long long ans, spt[N][L], dis[N];
vector<pair<int, int>> adj[N];
 
void dfs(int v, int p) {
	for (int i = 0; i < adj[v].size(); i++) {
		int u = adj[v][i].first, w = adj[v][i].second;
		if (u == p) {
			swap(adj[v].back(), adj[v][i]);
			adj[v].pop_back();
			if (i == adj[v].size())
				return;
			u = adj[v][i].first, w = adj[v][i].second;
		}
 
		par[u][0] = v;
		spt[u][0] = w;
		h[u] = h[v] + 1;
		dfs(u, v);
	}
}
 
void dfsu(int v, int p) {
	for (auto [u, w]: adj[v]) {
		dfsu(u, v);
		dis[v] = min(dis[v], dis[u] + w);
	}
}
 
void dfsd(int v, int p) {
	for (auto [u, w]: adj[v]) {
		dis[u] = min(dis[u], dis[v] + w);
		dfsd(u, v);
	}
}
 
long long distance(int v, int u) {
	long long res = 0;
	if (h[v] < h[u]) swap(v, u);
	for (int i = 0; i < L && res < ans; i++)
		if ((1 << i) & (h[v] - h[u])) {
			res += spt[v][i];
			v = par[v][i];
		}
	if (v == u) return res;
 
	for (int i = L - 1; i >= 0 && res < ans; i--)
		if (par[v][i] != par[u][i]) {
			res += spt[v][i] + spt[u][i];
			v = par[v][i];
			u = par[u][i];
		}
	return res + spt[v][0] + spt[u][0];
}
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		adj[A[i] + 1].push_back({B[i] + 1, D[i]});
		adj[B[i] + 1].push_back({A[i] + 1, D[i]});
	}
 
	dfs(1, 0);
	for (int i = 1; i < L; i++)
		for (int j = 1; j <= n; j++) {
			par[j][i] = par[par[j][i - 1]][i - 1];
			spt[j][i] = spt[j][i - 1] + spt[par[j][i - 1]][i - 1];
		}
}
 
long long Query(int S, int X[], int T, int Y[]) {
	ans = I;
	if (S < Q) {
		for (int i = 0; i < T; i++)
			for (int j = 0; j < S; j++)
				ans = min(ans, distance(Y[i] + 1, X[j] + 1));
		return ans;
	}
	
	for (int i = 0; i < N; dis[i++] = I);
	for (int i = 0; i < S; dis[X[i++] + 1] = 0); 
	dfsu(1, 0);
	dfsd(1, 0);
 
	for (int i = 0; i < T; i++)
		ans = min(ans, dis[Y[i] + 1]);
	return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 0; i < adj[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
factories.cpp:18:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |    if (i == adj[v].size())
      |        ~~^~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 35420 KB Output is correct
2 Correct 486 ms 41848 KB Output is correct
3 Correct 957 ms 41856 KB Output is correct
4 Correct 310 ms 41856 KB Output is correct
5 Correct 578 ms 42016 KB Output is correct
6 Correct 829 ms 41860 KB Output is correct
7 Correct 980 ms 41860 KB Output is correct
8 Correct 1086 ms 41864 KB Output is correct
9 Correct 571 ms 42020 KB Output is correct
10 Correct 835 ms 42068 KB Output is correct
11 Correct 985 ms 41860 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 1279 ms 187164 KB Output is correct
3 Correct 2131 ms 189008 KB Output is correct
4 Correct 812 ms 187968 KB Output is correct
5 Correct 2855 ms 204668 KB Output is correct
6 Correct 1825 ms 189268 KB Output is correct
7 Correct 1850 ms 69456 KB Output is correct
8 Correct 932 ms 69296 KB Output is correct
9 Correct 2590 ms 71252 KB Output is correct
10 Correct 1341 ms 69752 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 35420 KB Output is correct
2 Correct 486 ms 41848 KB Output is correct
3 Correct 957 ms 41856 KB Output is correct
4 Correct 310 ms 41856 KB Output is correct
5 Correct 578 ms 42016 KB Output is correct
6 Correct 829 ms 41860 KB Output is correct
7 Correct 980 ms 41860 KB Output is correct
8 Correct 1086 ms 41864 KB Output is correct
9 Correct 571 ms 42020 KB Output is correct
10 Correct 835 ms 42068 KB Output is correct
11 Correct 985 ms 41860 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1279 ms 187164 KB Output is correct
14 Correct 2131 ms 189008 KB Output is correct
15 Correct 812 ms 187968 KB Output is correct
16 Correct 2855 ms 204668 KB Output is correct
17 Correct 1825 ms 189268 KB Output is correct
18 Correct 1850 ms 69456 KB Output is correct
19 Correct 932 ms 69296 KB Output is correct
20 Correct 2590 ms 71252 KB Output is correct
21 Correct 1341 ms 69752 KB Output is correct
22 Correct 4239 ms 188244 KB Output is correct
23 Correct 2823 ms 189492 KB Output is correct
24 Correct 6177 ms 189720 KB Output is correct
25 Correct 6180 ms 191312 KB Output is correct
26 Execution timed out 8050 ms 189808 KB Time limit exceeded
27 Halted 0 ms 0 KB -