Submission #1109891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109891		Trisanu_Das	나일강 (IOI24_nile)	C++17	0 / 100	64 ms	12540 KiB

nile

#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 (stderr)

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
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18