제출 #44258

#제출 시각아이디문제언어결과실행 시간메모리
44258szawinis공장들 (JOI14_factories)C++17
15 / 100
6041 ms284040 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 1e17; int n; vector<int> sz; vector<vector<pair<int,int> > > g; vector<vector<int> > anc; vector<vector<ll> > d; vector<bool> block; vector<ll> mn; void init_dfs(int u, int par) { sz[u] = 1; for(auto p: g[u]) { int v, w; tie(v, w) = p; if(block[v] || v == par) continue; init_dfs(v, u); sz[u] += sz[v]; } } void calc(int src) { init_dfs(src, -1); int cen = src; while(true) { bool found = false; for(auto p: g[cen]) if(sz[p.first] < sz[cen] && sz[p.first] << 1 >= sz[src]) { cen = p.first; found = true; break; } if(!found) break; } block[cen] = true; queue<pair<int, int> > q; q.emplace(cen, -1); d[cen].push_back(0); anc[cen].push_back(cen); while(!q.empty()) { int u, par; tie(u, par) = q.front(); q.pop(); for(auto p: g[u]) if(p.first != par && !block[p.first]) { d[p.first].push_back(d[u].back() + p.second); anc[p.first].push_back(cen); q.emplace(p.first, u); } } for(auto p: g[cen]) if(!block[p.first]) calc(p.first); } void Init(int N, int A[], int B[], int D[]) { n = N; g.resize(n), sz.resize(n), anc.resize(n), d.resize(n), block.resize(n); mn.assign(n, INF); for(int i = 0; i < n-1; i++) { g[A[i]].emplace_back(B[i], D[i]); g[B[i]].emplace_back(A[i], D[i]); } calc(0); } ll Query(int S, int X[], int T, int Y[]) { ll ret = INF; for(int i = 0; i < S; i++) for(int j = 0; j < anc[X[i]].size(); j++) mn[anc[X[i]][j]] = min(d[X[i]][j], mn[anc[X[i]][j]]); for(int i = 0; i < T; i++) for(int j = 0; j < anc[Y[i]].size(); j++) ret = min(mn[anc[Y[i]][j]] + d[Y[i]][j], ret); for(int i = 0; i < S; i++) for(int j = 0; j < anc[X[i]].size(); j++) mn[anc[X[i]][j]] = INF; return ret; }

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

factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:69:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S; i++) for(int j = 0; j < anc[X[i]].size(); j++)
                                            ~~^~~~~~~~~~~~~~~~~~
factories.cpp:71:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < T; i++) for(int j = 0; j < anc[Y[i]].size(); j++)
                                            ~~^~~~~~~~~~~~~~~~~~
factories.cpp:73:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S; i++) for(int j = 0; j < anc[X[i]].size(); j++)
                                            ~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...