제출 #126605

#제출 시각아이디문제언어결과실행 시간메모리
126605fizzydavid공장들 (JOI14_factories)C++14
33 / 100
8015 ms140400 KiB
//by yjz #include "factories.h" #include<bits/stdc++.h> #define FF first #define SS second #define MP make_pair #define PB push_back typedef long long ll; using namespace std; const int maxn = 500111; int n; vector<pair<int,int> > con[maxn]; int fa[20][maxn], lv[maxn]; ll len[maxn]; int dfn[maxn], dtot; vector<pair<int,ll> > ncon[maxn]; int type[maxn]; void dfs(int x) { for (int i=1; i<20; i++) fa[i][x] = fa[i-1][fa[i-1][x]]; dfn[x] = ++dtot; for (auto e : con[x]) { int u = e.FF; if (u==fa[0][x]) continue; fa[0][u] = x; len[u] = len[x]+e.SS; lv[u] = lv[x]+1; dfs(u); } } int get_lca(int x, int y) { if (lv[x]>lv[y]) swap(x, y); for (int i=19; i>=0; i--) if (fa[i][y]&&lv[fa[i][y]]>=lv[x]) y = fa[i][y]; if (x==y) return x; for (int i=19; i>=0; i--) if (fa[i][x]!=fa[i][y]) { x = fa[i][x]; y = fa[i][y]; } return fa[0][x]; } void Init(int N, int A[], int B[], int D[]) { for (int i=0; i<maxn; i++) type[i] = 2; n = N; for (int i=0; i<n-1; i++) { int x = A[i], y = B[i], c = D[i]; x++; y++; con[x].PB(MP(y, c)); con[y].PB(MP(x, c)); } len[1] = 0; lv[1] = 1; dfs(1); } bool cmp(int x, int y) {return dfn[x]<dfn[y];} const ll inf = 4e18; void upd(ll &x, ll v) {x=min(x, v);} void add_edge(int x, int p) {ncon[p].PB(MP(x, len[x]-len[p]));}// cerr<<"add_edge:"<<p<<"->"<<x<<" "<<len[x]-len[p]<<endl;} ll ans; pair<ll,ll> calc_ans(int x) { pair<ll,ll> ret = MP(inf, inf); if (type[x]==0) ret.FF = 0; if (type[x]==1) ret.SS = 0; for (auto e : ncon[x]) { pair<ll,ll> pp = calc_ans(e.FF); upd(ret.FF, pp.FF+e.SS); upd(ret.SS, pp.SS+e.SS); } upd(ans, ret.FF+ret.SS); return ret; } long long Query(int S, int X[], int T, int Y[]) { vector<int> v; for (int i=0; i<S; i++) v.PB(X[i]+1), type[X[i]+1] = 0; for (int i=0; i<T; i++) v.PB(Y[i]+1), type[Y[i]+1] = 1; sort(v.begin(), v.end(), cmp); vector<int> st, all; st.PB(v[0]); all.PB(v[0]); for (int i=1; i<v.size(); i++) { int x = v[i]; int p = get_lca(x, st.back()); // cerr<<"x="<<x<<" last="<<st.back()<<" p="<<p<<endl; while (st.size()>=2&&len[st[st.size()-2]]>=len[p]) { add_edge(st.back(), st[st.size()-2]); st.pop_back(); } if (st.size()>0&&st.back()!=p) //add_edge p->left_most { add_edge(st.back(), p); st.pop_back(); } if (st.size()==0||st.back()!=p) st.PB(p), all.PB(p); if (x!=p) st.PB(x), all.PB(x); } ans = inf; assert(st.size()>0); while (st.size()>1) add_edge(st.back(), st[st.size()-2]), st.pop_back(); calc_ans(st[0]); for (auto t : all) ncon[t].clear(), type[t] = 2; return ans; }

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

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:86:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<v.size(); i++)
                ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...