제출 #656689

#제출 시각아이디문제언어결과실행 시간메모리
656689Hiennoob123공장들 (JOI14_factories)C++14
100 / 100
4528 ms293216 KiB
#include<bits/stdc++.h> #include "factories.h" #define ll long long #define ld long double #define cd complex<ld> #define pll pair<ll,ll> #define pii pair<int,int> #define pld pair<ld,ld> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std ; ll n ; ll num = 700 ; vector<pair<int , ll>> T[500005] ; vector<ll> Tc[500005] ; int depth[500005] ; ll dis[500005] ; int lg2[1000005] ; int Left[500005] ; bool check[500005] ; ll sz[500005] ; ll pa[500005] ; vector<int> euler ; vector<pair<int , int>> sparse[20] ; void build() { for(int i = 0 ; i< 20 ; i++) { if((1<<i)>euler.size()) break ; if(i==0) { sparse[0].assign(euler.size() , {0 , 0}) ; for(int j = 0 ; j< euler.size() ; j++) { sparse[0][j] = {depth[euler[j]], euler[j]} ; } } else { sparse[i].assign(euler.size()+1-(1<<i) , {0 , 0}) ; for(int j = 0 ; j< euler.size()-(1<<i)+1 ; j++) { sparse[i][j] = min(sparse[i-1][j] , sparse[i-1][j+(1<<(i-1))]) ; } } } } ll LCA(ll u , ll v) { u = Left[u] , v = Left[v] ; if(u>v) swap(u , v) ; int k = lg2[v-u+1] ; pair<int , ll> x = min(sparse[k][u] , sparse[k][v-(1<<k)+1]) ; return x.se ; } ll distance(ll u , ll v) { int k = LCA(u , v) ; return dis[u]+dis[v]-2*dis[k] ; } void dfs(ll v , ll par) { Left[v] = euler.size() ; euler.push_back(v) ; for(int i = 0 ; i< T[v].size() ; i++) { if(T[v][i].fi==par) continue ; dis[T[v][i].fi] = T[v][i].se+dis[v] ; depth[T[v][i].fi] = depth[v]+1 ; dfs(T[v][i].fi , v) ; euler.push_back(v) ; } } ll dfs_cnt(ll v , ll par) { sz[v] = 1 ; for(int i = 0 ; i< T[v].size() ; i++) { if(T[v][i].fi==par||check[T[v][i].fi]) continue ; sz[v] += dfs_cnt(T[v][i].fi , v) ; } return sz[v] ; } ll getcent(ll v , ll par , ll siz) { for(int i = 0 ; i< T[v].size() ; i++) { if(T[v][i].fi==par||check[T[v][i].fi]) continue ; if(sz[T[v][i].fi]*2>=siz) return getcent(T[v][i].fi , v , siz) ; } return v ; } void centroid(ll v , ll par) { ll k = getcent(v , -1 , dfs_cnt(v , -1)) ; //cout << k << " " << par << "\n" ; pa[k] = par ; if(par!=-1) { Tc[par].push_back(v) ; } check[k] = 1 ; for(int i = 0; i< T[k].size() ; i++) { if(check[T[k][i].fi]) continue ; centroid(T[k][i].fi , k) ; } } ll val[500005] = {} ; void Init(int N, int A[], int B[], int D[]) { n = N ; num = n ; for(int i = 0 ; i< n-1 ; i++) { T[A[i]].push_back(mp(B[i] , D[i])) ; T[B[i]].push_back(mp(A[i] , D[i])) ; } for(int i = 2 ; i<= 1000000 ; i++) lg2[i] = lg2[i/2]+1 ; dfs(0 , -1); build() ; centroid(0 , -1) ; for(int i = 0; i<= n; i++) val[i] = LLONG_MAX ; } ll Query(int N, int X[], int M, int Y[]) { //cout << -1 ; for(int i = 0 ; i< N ; i++) { ll cur = X[i] ; while(cur!=-1) { //cout << cur << "\n" ; val[cur] = min(val[cur] , dis[cur]+dis[X[i]]-2*dis[LCA(cur , X[i])] ); cur = pa[cur] ; } } ll ans = LLONG_MAX ; for(int i = 0; i < M ; i++) { ll cur = Y[i] ; while(cur!=-1) { //cout << cur << "\n" ; if(val[cur]!=LLONG_MAX) ans = min(ans , val[cur]+dis[cur]+dis[Y[i]]-2*dis[LCA(cur , Y[i])]) ; cur = pa[cur] ; } } for(int i = 0 ; i< N ; i++) { ll cur = X[i] ; while(cur!=-1) { val[cur] = LLONG_MAX ; cur = pa[cur] ; } } return ans; }

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

factories.cpp: In function 'void build()':
factories.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         if((1<<i)>euler.size()) break ;
      |            ~~~~~~^~~~~~~~~~~~~
factories.cpp:35:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int j = 0 ; j< euler.size() ; j++)
      |                             ~^~~~~~~~~~~~~~
factories.cpp:43:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int j = 0 ; j< euler.size()-(1<<i)+1 ; j++)
      |                             ~^~~~~~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs(long long int, long long int)':
factories.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'long long int dfs_cnt(long long int, long long int)':
factories.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'long long int getcent(long long int, long long int, long long int)':
factories.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'void centroid(long long int, long long int)':
factories.cpp:105:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0; i< T[k].size() ; i++)
      |                    ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...