제출 #166902

#제출 시각아이디문제언어결과실행 시간메모리
166902wmrmr공장들 (JOI14_factories)C++17
0 / 100
34 ms24568 KiB
#include <bits/stdc++.h> #include "factories.h" using namespace std; const int MAX = 5e5+10, LOG = 22; const long long int INF = 1e18; vector<int> g[MAX], p[MAX]; vector<int> rList; int troidProf[MAX], troidPai[LOG][MAX], sub[MAX]; long long int troidDist[LOG][MAX], mnDist[MAX]; bool isTroid[MAX], active[MAX]; void CalcSub(int v, int pai) { sub[v] = 1; for(int i=0;i<g[v].size();i++) { int prox = g[v][i]; if(prox == pai || isTroid[prox]) continue; CalcSub(prox,v); sub[v] += sub[prox]; } return; } int FindTroid(int v, int pai, int sz) { for(int i=0;i<g[v].size();i++) { int prox = g[v][i]; if( prox == pai || isTroid[prox] ) continue; if( sub[prox] > sz/2 ) return FindTroid(prox,v,sz); } return v; } void CalcDist(int v, int pai, int prof, int troid) { troidPai[prof][v] = troid; for(int i=0;i<g[v].size();i++) { int prox = g[v][i], peso = p[v][i]; if(prox == pai || isTroid[prox]) continue; troidDist[prof][prox] = troidDist[prof][v] + peso; CalcDist(prox,v,prof,troid); } return; } void Decompose(int v, int prof) { CalcSub(v,v); int troid = FindTroid(v,v,sub[v]); isTroid[troid] = 1; troidProf[troid] = prof; CalcDist(troid,troid,prof,troid); for(int i=0;i<g[troid].size();i++) { int prox = g[troid][i]; if(isTroid[prox]) continue; Decompose(prox,prof+1); } return; } void Init(int N, int A[], int B[], int D[]) { for(int i=0;i<N-1;i++) { g[ A[i] ].push_back( B[i] ); g[ B[i] ].push_back( A[i] ); p[ A[i] ].push_back( D[i] ); p[ B[i] ].push_back( D[i] ); } Decompose(0,0); return; } long long int Query(int S, int X[], int T, int Y[]) { long long int resp = INF; for(int i=0;i<S;i++) { int v = X[i]; for(int j=0;j<=troidProf[v];j++) { int troid = troidPai[j][v]; if(active[troid]) mnDist[troid] = min( mnDist[troid] , troidDist[j][v] ); else active[troid] = 1, mnDist[troid] = troidDist[j][v]; rList.push_back(troid); } } for(int i=0;i<T;i++) { int v = Y[i]; for(int j=1;j<=troidProf[v];j++) { int troid = troidPai[j][v]; if(!active[troid]) continue; resp = min( resp , mnDist[troid] + troidDist[j][v] ); } } for(int i=0;i<rList.size();i++) active[rList[i]] = 0; rList.clear(); return resp; }

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

factories.cpp: In function 'void CalcSub(int, int)':
factories.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
factories.cpp: In function 'int FindTroid(int, int, int)':
factories.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
factories.cpp: In function 'void CalcDist(int, int, int, int)':
factories.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
factories.cpp: In function 'void Decompose(int, int)':
factories.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[troid].size();i++)
              ~^~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:94:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<rList.size();i++) active[rList[i]] = 0;
              ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...