이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include "bits/stdc++.h"
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define ll long long
using namespace std;
set<pair<ll, ll>> conn[200005];
ll dp[200005][2];
bool vi[200005];
void dfs(int now) {
vi[now] = true;
ll cnta = 0, cntb = 0;
vector<ll> t;
t.clear();
t.pb(INT_MAX);
for(auto x: conn[now]) {
cerr << now << ' ' << x.fi << '\n';
if(vi[x.fi]) continue;
dfs(x.fi);
//cerr << now << ' ' << x.fi << ' ' << x.se << ' ' << dp[x.fi][0] << ' ' << dp[x.fi][1] + x.se << '\n';
cntb += dp[x.fi][0];
t.pb(min(dp[x.fi][0], dp[x.fi][1]) + x.se - dp[x.fi][0]);
}
cnta = cntb;
sort(t.begin(), t.end());
cnta += t[0];
int pt = 1;
while(t[pt] < 0) cnta += t[pt++];
//cerr << now << ' ' << cnta << ' ' << cntb << '\n';
//if(!yes) cnta += md;
cerr << now << ' ' << cnta << ' ' << cntb << '\n';
dp[now][0] = cnta;
dp[now][1] = cntb;
return;
}
long long min_total_length(vector<int> a, vector<int> b) {
int n = a.size(), m = b.size();
int pt = 0;
for(int i = 0; i < m; i++) {
while(pt + 1 < n && abs(a[pt + 1] - b[i]) < abs(b[i] - a[pt])) pt++;
if(pt + 1 < n && abs(a[pt + 1] - b[i]) == abs(b[i] - a[pt])) {
conn[n + i].insert(mp(pt, abs(b[i] - a[pt])));
conn[n + i].insert(mp(pt + 1, abs(b[i] - a[pt])));
conn[pt].insert(mp(n + i, abs(b[i] - a[pt])));
conn[pt + 1].insert(mp(n + i, abs(b[i] - a[pt])));
}
else {
conn[n + i].insert(mp(pt, abs(b[i] - a[pt])));
conn[pt].insert(mp(n + i, abs(b[i] - a[pt])));
}
//cerr << i << ' ' << pt << '\n';
}
pt = 0;
for(int i = 0; i < n; i++) {
while(pt + 1 < m && abs(b[pt + 1] - a[i]) < abs(a[i] - b[pt])) pt++;
if(pt + 1 < m && abs(b[pt + 1] - a[i]) == abs(a[i] - b[pt])) {
conn[i].insert(mp(n + pt, abs(a[i] - b[pt])));
conn[i].insert(mp(n + pt + 1, abs(a[i] - b[pt])));
conn[n + pt].insert(mp(i, abs(a[i] - b[pt])));
conn[n + pt + 1].insert(mp(i, abs(a[i] - b[pt])));
}
else {
conn[i].insert(mp(n + pt, abs(a[i] - b[pt])));
conn[n + pt].insert(mp(i, abs(a[i] - b[pt])));
}
//cerr << i << ' ' << pt << '\n';
}
ll ans = 0;
for(int i = 0; i < n + m; i++) {
if(!vi[i]) {
dfs(i);
ans += dp[i][0];
}
//cerr << i << ' ' << dp[i][0] << ' ' << dp[i][1] << '\n';
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |