| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 580275 | perchuts | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
vector<pair<int,ll>>g[maxn];
bool ok[maxn];
int par[maxn], lvl[maxn];
int findp(int x){return par[x] = (par[x]==x?x:findp(par[x]));}
bool merge(int x,int y){
x = findp(x), y = findp(y);
if(x==y)return 0;
if(lvl[x]<lvl[y])swap(x,y);
par[y] = x;
if(lvl[x]==lvl[y])lvl[x]++;
return 1;
}
bool mark[maxn][4];
ll dp[maxn][4];
ll dfs(int u,int p,int type){
if(mark[u][type])return dp[u][type];
mark[u][type] = 1;
if(type==0){
for(auto [v,c]:g[u]){
if(v==p)continue;
dp[u][0] += min(dfs(v,u,1),dfs(v,u,2));
}
}else if(type==1){
int cnt = 0;
ll sum = 0, best = 1e18;
for(auto [v,c]:g[u]){
if(v==p)continue;
ll pega = dfs(v,u,0) + c, naopega = min(dfs(v,u,1), dfs(v,u,2));
sum += min(pega,naopega), cnt += pega<=naopega;
ckmin(best,pega-naopega);
}
if(cnt==0)dp[u][1] = sum + best;
else dp[u][1] = sum;
}else if(type==2){
ll best = inf, sum = 0;
for(auto [v,c]:g[u]){
if(v==p)continue;
sum += min(dfs(v,u,1),dfs(v,u,2));
}
for(auto [v,c]:g[u]){
if(v==p)continue;
ckmin(best,sum-min(dfs(v,u,1),dfs(v,u,2))+dfs(v,u,3)+c);
}
dp[u][2] = best;
}else{
for(auto [v,c]:g[u]){
if(v==p)continue;
dp[u][3] += min({dfs(v,u,1),dfs(v,u,2),dfs(v,u,0)+c});
}
}
return dp[u][type];
}
ll min_total_length(vector<int> r, vector<int> b) {
int n = sz(r), m = sz(b);
for(int i=1;i<=n+m;++i)par[i] = i;
set<pair<ll,ii>>edges;
for(int i=0;i<n;++i){
int depois = lower_bound(all(b),r[i]) - begin(b);
if(depois!=m)edges.insert({ll(b[depois]-r[i]),{i+1,n+1+depois}});
if(depois!=0)edges.insert({ll(r[i]-b[depois-1]),{i+1,n+depois}});
}
for(int i=0;i<m;++i){
int depois = lower_bound(all(r),b[i]) - begin(r);
if(depois!=n)edges.insert({ll(r[depois]-b[i]),{depois+1,n+1+i}});
if(depois!=0)edges.insert({ll(b[i]-r[depois-1]),{depois,n+1+i}});
}
ll ans = 0;
for(auto [c,p]:edges){
auto [u,v] = p;
if(merge(u,v)){
g[u].pb({v,c}), g[v].pb({u,c});
}
}
return min(dfs(1,1,1),dfs(1,1,2));
}
int main(){
int n,m;cin>>n>>m;
vector<int>a(n), b(m);
for(auto& x:a)cin>>x;
for(auto& x:b)cin>>x;
cout<<min_total_length(a,b)<<endl;
}