이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |