제출 #236269

#제출 시각아이디문제언어결과실행 시간메모리
236269DS007공장들 (JOI14_factories)C++14
0 / 100
8053 ms121208 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") using namespace std; #define int long long const int N = 5e5; vector<pair<int, long long>> adj[N]; int n, m; /*int first[N], last[N], l2[N * 2], p2[N * 2]; long long dep[N]; int sparse[N * 2][22]; int c = 0;*/ int sub[N], par[N]; long long ans[N]; bool isCen[N]; int size = 0; int block_size, block_cnt; vector<int> first_visit; vector<int> euler_tour; vector<int> height; vector<int> log_2; vector<vector<int>> st; vector<vector<vector<int>>> blocks; vector<int> block_mask; long long dep[N]; void dfs(int v, int p, int h, long long de = 0) { first_visit[v] = euler_tour.size(); euler_tour.push_back(v); height[v] = h; dep[v] = de; for (auto u : adj[v]) { if (u.first == p) continue; dfs(u.first, v, h + 1, de + u.second); euler_tour.push_back(v); } } int min_by_h(int i, int j) { return height[euler_tour[i]] < height[euler_tour[j]] ? i : j; } void precompute_lca(int root) { // get euler tour & indices of first occurences first_visit.assign(n, -1); height.assign(n, 0); euler_tour.reserve(2 * n); dfs(root, -1, 0); // precompute all log values int m = euler_tour.size(); log_2.reserve(m + 1); log_2.push_back(-1); for (int i = 1; i <= m; i++) log_2.push_back(log_2[i / 2] + 1); block_size = max(1ll, log_2[m] / 2ll); block_cnt = (m + block_size - 1) / block_size; // precompute minimum of each block and build sparse table st.assign(block_cnt, vector<int>(log_2[block_cnt] + 1)); for (int i = 0, j = 0, b = 0; i < m; i++, j++) { if (j == block_size) j = 0, b++; if (j == 0 || min_by_h(i, st[b][0]) == i) st[b][0] = i; } for (int l = 1; l <= log_2[block_cnt]; l++) { for (int i = 0; i < block_cnt; i++) { int ni = i + (1 << (l - 1)); if (ni >= block_cnt) st[i][l] = st[i][l-1]; else st[i][l] = min_by_h(st[i][l-1], st[ni][l-1]); } } // precompute mask for each block block_mask.assign(block_cnt, 0); for (int i = 0, j = 0, b = 0; i < m; i++, j++) { if (j == block_size) j = 0, b++; if (j > 0 && (i >= m || min_by_h(i - 1, i) == i - 1)) block_mask[b] += 1 << (j - 1); } // precompute RMQ for each unique block int possibilities = 1 << (block_size - 1); blocks.resize(possibilities); for (int b = 0; b < block_cnt; b++) { int mask = block_mask[b]; if (!blocks[mask].empty()) continue; blocks[mask].assign(block_size, vector<int>(block_size)); for (int l = 0; l < block_size; l++) { blocks[mask][l][l] = l; for (int r = l + 1; r < block_size; r++) { blocks[mask][l][r] = blocks[mask][l][r - 1]; if (b * block_size + r < m) blocks[mask][l][r] = min_by_h(b * block_size + blocks[mask][l][r], b * block_size + r) - b * block_size; } } } } int lca_in_block(int b, int l, int r) { return blocks[block_mask[b]][l][r] + b * block_size; } int lca(int v, int u) { int l = first_visit[v]; int r = first_visit[u]; if (l > r) swap(l, r); int bl = l / block_size; int br = r / block_size; if (bl == br) return euler_tour[lca_in_block(bl, l % block_size, r % block_size)]; int ans1 = lca_in_block(bl, l % block_size, block_size - 1); int ans2 = lca_in_block(br, 0, r % block_size); int ans = min_by_h(ans1, ans2); if (bl + 1 < br) { int l = log_2[br - bl - 1]; int ans3 = st[bl+1][l]; int ans4 = st[br - (1 << l)][l]; ans = min_by_h(ans, min_by_h(ans3, ans4)); } return euler_tour[ans]; } // LCA begins /*void pre(int v, int p = -1, long long d = 0, int de = 0) { first[v] = c++; dep[v] = d; euler[c - 1] = v; depth[c - 1] = de; for (auto i : adj[v]) { if (i.first != p) { pre(i.first, v, d + i.second, de + 1); euler[c] = v; depth[c++] = de; } } last[v] = c - 1; } int merge(int a, int b) { return depth[a] < depth[b] ? a : b; } void build_sparse() { int es = n * 2 - 1; assert(es < N * 2); assert(l2[es] <= 22); for (int i = 0; i < es; i++) sparse[i][0] = i; for (int i = 1; i <= l2[es]; i++) { for (int j = 0; j < es && j - 1 + (p2[i]) < es; j++) sparse[j][i] = depth[sparse[j][i - 1]] < depth[sparse[j + (p2[i - 1])][i - 1]] ? sparse[j][i - 1] : sparse[j + (p2[i - 1])][i - 1]; } } int lca(int u, int v) { if (u == v) return u; int f1 = min(first[u], first[v]), f2 = max(first[v], first[u]), diff = f2 - f1; int dx = l2[diff]; return euler[merge(sparse[f1][dx], sparse[f2 - (p2[dx])][dx])]; }*/ long long dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } // LCA ends // Centroid decomposition begins void calc(int v, int p = -1) { // Pre calculate subtree sizes sub[v] = 1; size++; for (auto i : adj[v]) { if (i.first != p && !isCen[v]) calc(i.first, v), sub[v] += sub[i.first]; } } int find(int v, int p = -1) { // Find the centroid in current subtree for (auto i : adj[v]) { if (i.first != p && !isCen[i.first] && sub[i.first] > size / 2) return find(i.first, v); } return v; } void decompose(int v, int p = -1) { size = 0; // Stores size of current subtree calc(v); int centroid = find(v); par[centroid] = p; isCen[centroid] = true; for (auto i : adj[centroid]) { if (i.first != p && !isCen[i.first]) decompose(i.first, centroid); } } // Centroid decomposition ends void update(int v) { int p = v, co = 0; while (p != -1) { ans[p] = min(ans[p], dist(p, v)); p = par[p]; } assert(co <= 22); } long long query(int v) { int p = v, co = 0; long long val = 1e18; while (p != -1) { val = min(val, ans[p] + dist(p, v)); p = par[p]; } assert(co <= 22); return val; } void revert(int v) { int p = v; while (p != -1) { ans[p] = 1e18; p = par[p]; } } #undef int int qc = 0; long long Query(int S, int X[], int T, int Y[]) { if (S <= 10 && T <= 10) { long long ans = dist(X[0], Y[0]); for (int i = 0; i < S; i++) { for (int j = 0; j < T; j++) ans = min(ans, dist(X[i], Y[j])); } qc++; return ans; } else for(;;); for (int i = 0; i < S; i++) update(X[i]); long long ans = 1e18; for (int i = 0; i < T; i++) ans = min(ans, query(Y[i])); for (int i = 0; i < S; i++) revert(X[i]); return ans; } void Init(int N, int A[], int B[], int D[]) { n = N; for (int i = 0; i < n - 1; i++) { adj[A[i]].emplace_back(B[i], D[i]); adj[B[i]].emplace_back(A[i], D[i]); } precompute_lca(0); //decompose(0); fill(ans, ans + N, 1e18); }

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
factories.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...