제출 #387686

#제출 시각아이디문제언어결과실행 시간메모리
387686arujbansal공장들 (JOI14_factories)C++17
컴파일 에러
0 ms0 KiB
#include "factories.h" #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #include <array> #include <stack> #include <queue> #include <random> #include <numeric> #include <functional> #include <chrono> #include <utility> #include <iomanip> #include <assert.h> using namespace std; void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define rng_seed(x) mt19937 rng(x) #define all(x) (x).begin(), (x).end() #define sz(x) (int) (x).size() // #define int long long using ll = long long; const int MXN = 5e5 + 5, MXK = 19; const ll INF = 1e18; vector<pair<int, ll>> g[MXN]; int cd_par[MXN], binlift_par[MXN][MXK], tin[MXN], tout[MXN], subtree[MXN]; ll binlift_dist[MXN][MXK], best[MXN]; bool vis[MXN]; int timer; void dfs1(int u, int p) { tin[u] = timer++; for (int j = 1; j < MXK; j++) { binlift_par[u][j] = binlift_par[binlift_par[u][j - 1]][j - 1]; binlift_dist[u][j] = binlift_dist[u][j - 1] + binlift_dist[binlift_par[u][j - 1]][j - 1]; } for (const auto &[v, w] : g[u]) { if (v == p) continue; binlift_par[v][0] = u; binlift_dist[v][0] = w; dfs1(v, u); } tout[u] = timer - 1; } bool is_anc(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int query_lca(int u, int v) { if (is_anc(u, v)) return u; if (is_anc(v, u)) return v; for (int j = MXK - 1; j >= 0; j--) { int lift = binlift_par[u][j]; if (!is_anc(lift, v)) u = lift; } return binlift_par[u][0]; } int query_dist(int u, int v) { if (u == v) return 0; ll res = 0; for (int j = MXK - 1; j >= 0; j--) { int lift = binlift_par[u][j]; if (!is_anc(lift, v)) { res += binlift_dist[u][j]; u = lift; } } return res + binlift_dist[u][0]; } ll dist(int u, int v) { if (u == v) return 0; int cur_lca = query_lca(u, v); return query_dist(u, cur_lca) + query_dist(v, cur_lca); } void dfs_subtree(int u, int p) { subtree[u] = 1; for (const auto &[v, w] : g[u]) { if (v == p || vis[v]) continue; dfs_subtree(v, u); subtree[u] += subtree[v]; } } int centroid(int u, int p, int vertices) { for (const auto &[v, w] : g[u]) { if (v == p || vis[v]) continue; if (subtree[v] * 2 > vertices) return centroid(v, u, vertices); } return u; } void build_cd(int u, int p) { dfs_subtree(u, -1); int c = centroid(u, -1, subtree[u]); if (p == -1) p = c; cd_par[c] = p; vis[c] = true; for (const auto &[v, w] : g[c]) { if (vis[v]) continue; build_cd(v, c); } } void build_factory(int u) { int v = u; best[v] = 0; do { v = cd_par[v]; best[v] = min(best[v], dist(u, v)); } while (v != cd_par[v]); } void remove_factory(int v) { best[v] = INF; do { v = cd_par[v]; best[v] = INF; } while (v != cd_par[v]); } ll query_factory(int u) { int v = u; ll ans = best[v]; do { v = cd_par[v]; ans = min(ans, dist(u, v) + best[v]); } while (v != cd_par[v]); return ans; } void init(int N, int A[], int B[], int D[]) { for (int i = 0; i < N - 1; i++) { g[A[i]].emplace_back(B[i], D[i]); g[B[i]].emplace_back(A[i], D[i]); } dfs1(0, -1); build_cd(0, -1); for (int i = 1; i <= N; i++) best[i] = INF; } ll query(int S, int X[], int T, int Y[]) { ll ans = INF; for (const auto &v : X) build_factory(v); for (const auto &v : Y) ans = min(ans, query_factory(v)); for (const auto &v : X) remove_factory(v); return ans; } // void solve() { // int N, Q; // cin >> N >> Q; // vector<int> A(N - 1), B(N - 1), D(N - 1); // for (int i = 0; i < N - 1; i++) // cin >> A[i] >> B[i] >> D[i]; // Init(N, A, B, D); // while (Q--) { // int S, T; // cin >> S >> T; // vector<int> X(S), Y(T); // for (auto &x : X) cin >> x; // for (auto &x : Y) cin >> x; // cout << Query(S, X, T, Y) << "\n"; // } // // for (int i = 0; i < N; i++) { // // for (int j = i + 1; j < N; j++) { // // dbg(i, j, dist(i, j)); // // } // // } // // dbg(query_lca(5, 6), query_dist(5, 1)); // // for (int j = 0; j < MXK; j++) // // dbg(j, binlift_dist[5][j]); // } // signed main() { // ios_base::sync_with_stdio(false); // cin.tie(nullptr); // int TC = 1; // // cin >> TC; // while (TC--) solve(); // }

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

factories.cpp: In function 'll query(int, int*, int, int*)':
factories.cpp:186:26: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
  186 |     for (const auto &v : X)
      |                          ^
      |                          std::begin
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from factories.cpp:3:
/usr/include/c++/9/bits/range_access.h:105:37: note: 'std::begin' declared here
  105 |   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&);
      |                                     ^~~~~
factories.cpp:186:26: error: 'end' was not declared in this scope; did you mean 'std::end'?
  186 |     for (const auto &v : X)
      |                          ^
      |                          std::end
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from factories.cpp:3:
/usr/include/c++/9/bits/range_access.h:107:37: note: 'std::end' declared here
  107 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&);
      |                                     ^~~
factories.cpp:189:26: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
  189 |     for (const auto &v : Y)
      |                          ^
      |                          std::begin
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from factories.cpp:3:
/usr/include/c++/9/bits/range_access.h:105:37: note: 'std::begin' declared here
  105 |   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&);
      |                                     ^~~~~
factories.cpp:189:26: error: 'end' was not declared in this scope; did you mean 'std::end'?
  189 |     for (const auto &v : Y)
      |                          ^
      |                          std::end
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from factories.cpp:3:
/usr/include/c++/9/bits/range_access.h:107:37: note: 'std::end' declared here
  107 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&);
      |                                     ^~~
factories.cpp:192:26: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
  192 |     for (const auto &v : X)
      |                          ^
      |                          std::begin
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from factories.cpp:3:
/usr/include/c++/9/bits/range_access.h:105:37: note: 'std::begin' declared here
  105 |   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&);
      |                                     ^~~~~
factories.cpp:192:26: error: 'end' was not declared in this scope; did you mean 'std::end'?
  192 |     for (const auto &v : X)
      |                          ^
      |                          std::end
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from factories.cpp:3:
/usr/include/c++/9/bits/range_access.h:107:37: note: 'std::end' declared here
  107 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&);
      |                                     ^~~