제출 #156804

#제출 시각아이디문제언어결과실행 시간메모리
156804Alexa2001공장들 (JOI14_factories)C++17
15 / 100
8026 ms338908 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> Pair; const int Nmax = 5e5 + 5; const ll lim = 1e17; vector<ll> h[Nmax]; vector<int> root[Nmax]; vector<int> v[Nmax], c[Nmax]; int w[Nmax]; bool used[Nmax]; int n, All; ll best[Nmax]; void dfs0(int node, int dad = -1) { w[node] = 1; for(auto it : v[node]) if(!used[it] && it!=dad) { dfs0(it, node); w[node] += w[it]; } } Pair centroid(int node, int dad = -1) { int worst = All - w[node]; Pair best = {n, n}; for(auto it : v[node]) if(!used[it] && it != dad) { best = min(best, centroid(it, node)); worst = max(worst, w[it]); } best = min(best, {worst, node}); return best; } void dfs(int node, int dad = -1) { int i; for(i=0; i<v[node].size(); ++i) { int son, cost; son = v[node][i], cost = c[node][i]; if(used[son] || son == dad) continue; h[son].push_back(h[node].back() + cost); root[son].push_back(root[node].back()); dfs(son, node); } } void build(int node) { dfs0(node); All = w[node]; node = centroid(node).second; h[node].push_back(0); root[node].push_back(node); dfs(node); used[node] = 1; for(auto it : v[node]) if(!used[it]) build(it); } void Init(int N, int A[], int B[], int D[]) { n = N; int i; for(i=0; i<n-1; ++i) { v[A[i]].push_back(B[i]); v[B[i]].push_back(A[i]); c[A[i]].push_back(D[i]); c[B[i]].push_back(D[i]); } for(i=0; i<n; ++i) best[i] = lim; build(0); } static void min_to(ll &x, ll y) { if(x > y) x = y; } ll Query(int S, int X[], int T, int Y[]) { int i, j; vector<pair<int,ll>> S1, S2; for(i=0; i<S; ++i) { int node = X[i]; for(j=0; j<root[node].size(); ++j) min_to( best[root[node][j]], h[node][j] ); } ll ans = lim; for(i=0; i<T; ++i) { int node = Y[i]; for(j=0; j<root[node].size(); ++j) min_to(ans, best[root[node][j]] + h[node][j] ); } for(i=0; i<S; ++i) { int node = X[i]; for(j=0; j<root[node].size(); ++j) best[root[node][j]] = lim; } return ans; }

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

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<root[node].size(); ++j)
                  ~^~~~~~~~~~~~~~~~~~
factories.cpp:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<root[node].size(); ++j)
                  ~^~~~~~~~~~~~~~~~~~
factories.cpp:132:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<root[node].size(); ++j)
                  ~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...