oj.uz

답안 #1109891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109891 2024-11-08T02:51:14 Z Trisanu_Das 나일강 (IOI24_nile) C++17
0 / 100
 64 ms 12540 KB 
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define ll long long
const int N = 3e5 + 5;

int par[N];
int sbtr[N];
int H;

void init(int n) {
    H = 2 * n;
    for (int i = 0; i < n; i++) {
        par[i] = i;
        sbtr[i] = 1;
    }
}

int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
}

void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;

    if (sbtr[py] > sbtr[px]) swap(px, py);
    int a = sbtr[px], b = sbtr[py];
    sbtr[px] += sbtr[py];
    par[py] = px;

    if (a % 2 == 1 && b % 2 == 1) H -= 2;
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size();
    init(n);

    int q = E.size();

    if (q <= 5) {
        vector<ll> ans;
        vector<pair<ll, ll>> v;

        for (int i = 0; i < n; i++) {
            v.pb({W[i], i});
        }
        sort(v.begin(), v.end());

        for (int f = 0; f < q; f++) {
            ll d = E[f];
            vector<vector<ll>> dp(n + 5, vector<ll>(2, 1e17));

            for (int i = 0; i < n; i++) {
                int a = v[i].ss;
                int b = i > 0 ? v[i - 1].ss : -1;
                int c = i > 1 ? v[i - 2].ss : -1;

                if (i > 0 && abs(W[a] - W[b]) <= d) {
                    dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] - A[b] + B[b] + B[a]);
                }
                if (i > 1 && abs(W[a] - W[c]) <= d) {
                    dp[i + 1][1] = min(dp[i + 1][1], dp[i - 1][0] - A[c] + B[c] + B[a] + A[b]);
                }
                dp[i + 1][0] = min(dp[i + 1][0], min(dp[i][1], dp[i][0]) + A[a]);
            }

            ans.pb(min(dp[n][0], dp[n][1]));
        }
        return ans;
    }

    vector<ll> ans(q);
    vector<pair<ll, ll>> v;
    vector<pair<ll, pair<int, int>>> vc;

    for (int i = 0; i < n; i++) {
        v.pb({W[i], i});
    }
    sort(v.begin(), v.end());

    for (int i = 1; i < n; i++) {
        int x = abs(v[i].ff - v[i - 1].ff);
        int a = v[i - 1].ss, b = v[i].ss;
        vc.pb({x, {a, b}});
    }
    sort(vc.begin(), vc.end());

    int idx = 0;
    vector<pair<int, int>> vec;
    for (int i = 0; i < q; i++) {
        vec.pb({E[i], i});
    }
    sort(vec.begin(), vec.end());

    for (int f = 0; f < q; f++) {
        ll d = vec[f].ff;
        int k = vec[f].ss;

        while (idx < vc.size() && vc[idx].ff <= d) {
            int a = vc[idx].ss.ff, b = vc[idx].ss.ss;
            unite(a, b);
            idx++;
        }
        ans[k] = H;
    }

    return ans;
}

Compilation message

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:104:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         while (idx < vc.size() && vc[idx].ff <= d) {
      |                ~~~~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 12540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 12540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 12540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -