제출 #707266

#제출 시각아이디문제언어결과실행 시간메모리
707266Danilo21공장들 (JOI14_factories)C++17
100 / 100
4563 ms370644 KiB
#include <bits/stdc++.h> #include "factories.h" #define ll long long #define ld long double #define pb push_back #define fi first #define se second #define en '\n' #define sp ' ' #define tb '\t' #define ri(n) int n; cin >> n #define rl(n) ll n; cin >> n #define rs(s) string s; cin >> s #define rc(c) char c; cin >> c #define rv(v) for (auto &x : v) cin >> x #define pven(v) for (auto x : v) cout << x << en #define pv(v) for (auto x : v) cout << x << sp; cout << en #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define yes cout << "Yes" << en #define no cout << "No" << en #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) #define ssort(a, b) if (a < b) swap(a, b) #define bitcnt(a) (__builtin_popcountll(a)) #define bithigh(a) (63-__builtin_clzll(a)) #define lg bithigh #define highpow(a) (1LL << (ll)lg(a)) using namespace std; class Sparse{ int n; vector<ll> a; vector<vector<int> > lookup; public: Sparse(){} Sparse(const vector<ll>& A){ Assign(A); } void Assign(const vector<ll>& A){ n = A.size(); a = A; lookup.assign(n, vector<int>(lg(n)+1, -1)); for (int i = 0; i < n; i++) lookup[i][0] = i; for (int d = 1; d <= lg(n); d++){ for (int i = 0; i < n; i++){ if (i + (1 << (d-1)) < n){ int x = lookup[i][d-1], y = lookup[i+(1<<(d-1))][d-1]; lookup[i][d] = (!~y || a[x] < a[y] ? x : y); } } } } int query(int l, int r) const { int d = highpow(r-l+1); int x = lookup[l][lg(d)], y = lookup[r-d+1][lg(d)]; return (a[x] < a[y] ? x : y); } }; const ll LINF = 1e18; const int mxN = 1e6+10, INF = 2e9; ll n, dist[mxN], in[mxN], out[mxN]; vector<array<ll, 2> > g[mxN]; vector<ll> e, d; Sparse E; int Lca(int u, int v){ if (in[u] > in[v]) swap(u, v); return e[E.query(in[u], out[v])]; } ll Dist(int u, int v){ int s = Lca(u, v); return dist[u] + dist[v] - 2*dist[s]; } void Euler(int s = 0, int p = -1, ll dep = 0){ dist[s] = dep; in[s] = e.size(); e.pb(s); d.pb(dep); for (auto [u, w] : g[s]){ if (u^p){ Euler(u, s, dep+w); e.pb(s); d.pb(dep); } } out[s] = e.size(); e.pb(s); d.pb(dep); } void Init(int N, int A[], int B[], int D[]){ n = N; for (int i = 0; i < n-1; i++){ g[A[i]].pb({B[i], D[i]}); g[B[i]].pb({A[i], D[i]}); } Euler(); E.Assign(d); } void Build(int N, int A[], vector<array<int, 2> >& e, vector<ll>& d){ for (int i = 0; i < N; i++){ e.pb({in[A[i]], A[i]}); e.pb({out[A[i]], A[i]}); } sort(all(e)); for (auto [i, s] : e) d.pb(dist[s]); } int BSL(int x, const vector<array<int, 2> >& a){ int l = 0, r = a.size()-1, ans = a.size(); while (l <= r){ int k = (l + r + 1)>>1; if (a[k][0] >= x){ ans = k; r = k - 1; } else l = k + 1; } return ans; } int BSR(int x, const vector<array<int, 2> >& a){ int l = 0, r = a.size()-1, ans = -1; while (l <= r){ int k = (l + r + 1)>>1; if (a[k][0] <= x){ ans = k; l = k + 1; } else r = k - 1; } return ans; } long long Query(int S, int X[], int T, int Y[]){ vector<array<int, 2> > eX, eY; vector<ll> dX, dY; Build(S, X, eX, dX); Build(T, Y, eY, dY); Sparse sX(dX), sY(dY); vector<int> a; for (auto [i, s] : eX) a.pb(i); for (auto [i, s] : eY) a.pb(i); sort(all(a)); vector<int> A; for (int i = 0; i < a.size()-1; i++) A.pb(e[E.query(a[i], a[i+1])]); ll ans = LINF; for (int s : A){ int i = BSL(in[s], eX), j = BSR(out[s], eX); if (i > j) continue; int u = eX[sX.query(i, j)][1]; i = BSL(in[s], eY); j = BSR(out[s], eY); if (i > j) continue; int v = eY[sY.query(i, j)][1]; smin(ans, Dist(u, v)); } return ans; }

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

factories.cpp: In function 'void Build(int, int*, std::vector<std::array<int, 2> >&, std::vector<long long int>&)':
factories.cpp:115:22: warning: narrowing conversion of 'in[(*(A + ((sizetype)(((long unsigned int)i) * 4))))]' from 'long long int' to 'int' [-Wnarrowing]
  115 |         e.pb({in[A[i]], A[i]});
      |               ~~~~~~~^
factories.cpp:116:23: warning: narrowing conversion of 'out[(*(A + ((sizetype)(((long unsigned int)i) * 4))))]' from 'long long int' to 'int' [-Wnarrowing]
  116 |         e.pb({out[A[i]], A[i]});
      |               ~~~~~~~~^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:162:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for (int i = 0; i < a.size()-1; i++)
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...