제출 #118633

#제출 시각아이디문제언어결과실행 시간메모리
118633evpipis공장들 (JOI14_factories)C++17
100 / 100
7918 ms283272 KiB
#include <bits/stdc++.h> #include "factories.h" using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair typedef long long ll; typedef pair<int, int> ii; const int len = 5e5+5, lg = 19; const ll inf = 1e17; int dep[len], ord[len], tp[len], cnt; pair<int, ll> par[len], up[lg][len]; ll dp[len][2]; vector<int> vec, st; vector<ii> adj[len]; vector<pair<int, ll> > nex[len]; void fix(int u){ ord[u] = cnt++; for (int j = 0; j < adj[u].size(); j++){ ii v = adj[u][j]; if (v.fi == par[u].fi) continue; par[v.fi] = mp(u, v.se); dep[v.fi] = dep[u]+1; fix(v.fi); } } int lca(int a, int b){ if (a == 0 || b == 0) return 0; if (dep[a] < dep[b]) swap(a, b); for (int j = lg-1; j >= 0; j--) if ((1<<j)&(dep[a]-dep[b])) a = up[j][a].fi; if (a == b) return a; for (int j = lg-1; j >= 0; j--) if (up[j][a].fi != up[j][b].fi) a = up[j][a].fi, b = up[j][b].fi; return par[a].fi; } void Init(int n, int A[], int B[], int D[]){ for (int i = 0; i < n-1; i++){ int a = A[i]+1, b = B[i]+1, c = D[i]; adj[a].pb(mp(b, c)); adj[b].pb(mp(a, c)); } cnt = dep[1] = 1; fix(1); for (int i = 1; i <= n; i++) up[0][i] = par[i]; for (int j = 1; (1<<j) < n; j++) for (int i = 1; i <= n; i++) if (up[j-1][i].fi != 0){ up[j][i] = up[j-1][up[j-1][i].fi]; up[j][i].se += up[j-1][i].se; } for (int i = 0; i <= n; i++) tp[i] = 2; } bool comp(int a, int b){ return (ord[a] < ord[b]); } ll path(int a, int b){ ll ans = 0; for (int j = lg-1; j >= 0; j--) if ((1<<j)&(dep[a]-dep[b])) ans += up[j][a].se, a = up[j][a].fi; return ans; } ll dfs(int u){ //printf("inside dfs: u = %d\n", u); ll ans = inf; dp[u][0] = dp[u][1] = inf; if (tp[u] == 0) dp[u][0] = 0; if (tp[u] == 1) dp[u][1] = 0; for (int j = 0; j < nex[u].size(); j++){ pair<int, ll> v = nex[u][j]; ans = min(ans, dfs(v.fi)); dp[u][0] = min(dp[u][0], dp[v.fi][0]+v.se); dp[u][1] = min(dp[u][1], dp[v.fi][1]+v.se); } ans = min(ans, dp[u][0]+dp[u][1]); //clear everything tp[u] = 2; nex[u].clear(); return ans; } ll Query(int s, int X[], int t, int Y[]){ for (int i = 0; i < s; i++) vec.pb(X[i]+1), tp[vec.back()] = 0; for (int i = 0; i < t; i++) vec.pb(Y[i]+1), tp[vec.back()] = 1; sort(vec.begin(), vec.end(), comp); st.pb(0); for (int i = 0; i < vec.size(); i++){ int u = vec[i], p = lca(u, st.back()); //printf("virtual tree... u = %d, back = %d, lca = %d\n", u, st.back(), p); while (st.size() >= 2 && dep[p] <= dep[st[st.size()-2]]){ int v = st.back(); st.pop_back(); nex[st.back()].pb(mp(v, path(v, st.back()))); } if (p != st.back()){ nex[p].pb(mp(st.back(), path(st.back(), p))); st.pop_back(); st.pb(p); } st.pb(u); } for (int i = 0; i+1 < st.size(); i++) nex[st[i]].pb(mp(st[i+1], path(st[i+1], st[i]))); ll ans = dfs(0); st.clear(); vec.clear(); return ans; }

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

factories.cpp: In function 'void fix(int)':
factories.cpp:23:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'll dfs(int)':
factories.cpp:98:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < nex[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~
factories.cpp:144:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i+1 < st.size(); i++)
                     ~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...