제출 #580276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580276		perchuts	전선 연결 (IOI17_wiring)	C++17	0 / 100	229 ms	53052 KiB

wiring

#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);
#include "wiring.h"

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;
// }

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

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:96:8: warning: unused variable 'ans' [-Wunused-variable]
   96 |     ll ans = 0;
      |        ^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45