oj.uz

답안 #416822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
416822 2021-06-03T03:08:28 Z kevinxiehk 전선 연결 (IOI17_wiring) C++17
0 / 100
 8 ms 9676 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9676 KB 3rd lines differ - on the 1st token, expected: '25859', found: '2147519111'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 9676 KB 3rd lines differ - on the 1st token, expected: '904', found: '2147484535'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9676 KB 3rd lines differ - on the 1st token, expected: '316', found: '2147483943'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9676 KB 3rd lines differ - on the 1st token, expected: '27', found: '4294967315'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9676 KB 3rd lines differ - on the 1st token, expected: '25859', found: '2147519111'
2 Halted 0 ms 0 KB -