제출 #529874

#제출 시각아이디문제언어결과실행 시간메모리
529874Lobo공장들 (JOI14_factories)C++17
100 / 100
4484 ms490512 KiB
#include "factories.h" #include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; // #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define maxn 500050 int n, szfc[maxn], block[maxn], h[maxn], pc[maxn], tin[maxn], tout[maxn]; pair<int,int> mnr[2*maxn][23], mnl[2*maxn][23]; long long d[maxn], mn[maxn]; vector<int> vfc; vector<pair<int,int>> g[maxn], el; void dfsfc(int u, int ant) { szfc[u] = 1; vfc.pb(u); for(auto V : g[u]) { int v = V.fr; if(v == ant || block[v]) continue; dfsfc(v,u); szfc[u]+= szfc[v]; } } void dfslca(int u, int ant) { tin[u] = el.size(); el.pb(mp(h[u],u)); for(auto V : g[u]) { int v = V.fr; int w = V.sc; if(v == ant) continue; h[v] = h[u]+1; d[v] = d[u]+w; dfslca(v,u); el.pb(mp(h[u],u)); } tout[u] = el.size()-1; } int lca(int u, int v) { if(tin[u] >= tin[v] && tout[u] <= tout[v]) { return v; } else if(tin[v] >= tin[u] && tout[v] <= tout[u]) { return u; } if(tin[u] > tin[v]) { swap(u,v); } int l = tout[u]; int r = tin[v]; int p = 31-__builtin_clz(r-l+1); auto x = min(mnr[l][p], mnl[r][p]); return x.sc; } int fcent(int beg) { vfc.clear(); dfsfc(beg,beg); int cent = beg; for(auto u : vfc) { bool ok = true; if(szfc[beg]-szfc[u] > szfc[beg]/2) ok = false; for(auto V : g[u]) { int v = V.fr; if(block[v]) continue; if(szfc[v] > szfc[u]) continue; if(szfc[v] > szfc[beg]/2) ok = false; } if(ok) cent = u; } block[cent] = 1; for(auto V : g[cent]) { int v = V.fr; if(block[v]) continue; pc[fcent(v)] = cent; } return cent; } long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) { long long ans = inf; for(int i = 0; i < S; i++) { int v = X[i]; while(v != -1) { mn[v] = min(mn[v],d[X[i]]+d[v]-2*d[lca(X[i],v)]); v = pc[v]; } } for(int i = 0; i < T; i++) { int v = Y[i]; while(v != -1) { ans = min(ans, mn[v]+d[Y[i]]+d[v]-2*d[lca(Y[i],v)]); v = pc[v]; } } for(int i = 0; i < S; i++) { int v = X[i]; while(v != -1) { mn[v] = inf; v = pc[v]; } } return ans; } void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) { n = N; for(int i = 0; i < n-1; i++) { g[A[i]].pb(mp(B[i],D[i])); g[B[i]].pb(mp(A[i],D[i])); } for(int i = 0; i < n; i++) { pc[i] = -1; mn[i] = inf; } fcent(0); dfslca(0,0); for(int i = 0; i < el.size(); i++) { mnr[i][0] = el[i]; } for(int j = 1; j <= 21; j++) { for(int i = 0; i < el.size(); i++) { mnr[i][j] = min(mnr[i][j-1],mnr[min((int) el.size()-1, i+(1<<(j-1)))][j-1]); } } for(int i = 0; i < el.size(); i++) { mnl[i][0] = el[i]; } for(int j = 1; j <= 21; j++) { for(int i = 0; i < el.size(); i++) { mnl[i][j] = min(mnl[i][j-1],mnl[max(0, i-(1<<(j-1)))][j-1]); } } } // int32_t main() { // ios::sync_with_stdio(false); cin.tie(0); // freopen("in.in", "r", stdin); // //freopen("out.out", "w", stdout); // int32_t N, Q; cin >> N >> Q; // int32_t 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--) { // int32_t S, T; cin >> S >> T; // int32_t X[S], Y[T]; // for(int i = 0; i < S; i++) cin >> X[i]; // for(int i = 0; i < T; i++) cin >> Y[i]; // cout << Query(S,X,T,Y) << endl; // } // }

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

factories.cpp: In function 'void Init(int32_t, int32_t*, int32_t*, int32_t*)':
factories.cpp:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(int i = 0; i < el.size(); i++) {
      |                    ~~^~~~~~~~~~~
factories.cpp:145:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for(int i = 0; i < el.size(); i++) {
      |                        ~~^~~~~~~~~~~
factories.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for(int i = 0; i < el.size(); i++) {
      |                    ~~^~~~~~~~~~~
factories.cpp:154:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         for(int i = 0; i < el.size(); i++) {
      |                        ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...