Submission #416823

#	Time	Username	Problem	Language	Result	Execution time	Memory
416823		kevinxiehk	Wiring (IOI17_wiring)	C++17	0 / 100	6 ms	9676 KiB

wiring

#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.pb(INT_MAX);
    for(auto x: conn[now]) {
        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(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;
}

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