Submission #1109890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109890		Trisanu_Das	Nile (IOI24_nile)	C++17	67 / 100	63 ms	21296 KiB

nile

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;

int par[300005], sz[300005], res;

void make(int n){
    res = 2 * n;
    for(int i = 0; i < n; i++){
        par[i] = i;
        sz[i] = 1;
    }
}

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

void unite(int u, int v){
    u = find(u); v = find(v);
    if(u == v) return;
    if(sz[v] > sz[u]) swap(u, v);
    if((sz[v] & 1) && (sz[u] & 1)) res -= 2;
    par[v] = u;
    sz[u] += sz[v];
}
 
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
    int N = W.size(), Q = E.size();
    vector<ll> ans;
    if(Q <= 5){
        vector<tuple<int, int, int> > items;
        for(int i = 0; i < N; ++i) items.push_back(make_tuple(W[i], A[i], B[i]));
        sort(items.begin(), items.end());
        sort(items.begin(), items.end());
        for (int i = 0; i < N; ++i) {
            auto [w, a, b] = items[i];
            W[i] = w, A[i] = a, B[i] = b;
        }
        for(int i = 0; i < Q; ++i){
            int d = E[i];
            vector<ll> dp(N + 1, LLONG_MAX);
            for(int i = 0; i < N; ++i){
                if(i == 0) dp[i] = (ll)A[i];
                else if(i == 1){
                    if(W[i] - W[i - 1] <= d) dp[i] = (ll)B[i] + (ll)B[i - 1];
                    else dp[i] = dp[i - 1] + (ll)A[i];
                }
                else{
                    dp[i] = dp[i - 1] + (ll)A[i];
                    if(W[i] - W[i - 1] <= d) dp[i] = min(dp[i], (ll)((ll)B[i] + (ll)B[i - 1] + dp[i - 2]));
                    if(W[i] - W[i - 2] <= d){
                        if(i >= 3) dp[i] = min(dp[i], (ll)((ll)B[i] + (ll)A[i - 1] + (ll)B[i - 2] + dp[i - 3]));
                        else dp[i] = min(dp[i], (ll)((ll)B[i] + (ll)A[i - 1] + (ll)B[i - 2]));
                    }
                }
            }
            ans.push_back(dp[N - 1]);
        }
    }else{
        vector<pair<ll, ll> > v;
        vector<pair<ll, pair<int, int> > > vv;
        for(int i = 0; i < N; i++) v.push_back({W[i], i});
        sort(v.begin(), v.end());
        for(int i = 1; i < N; i++) vv.push_back({v[i].ff - v[i - 1].ff, {v[i - 1].ss, v[i].ss}});
        sort(vv.begin(), vv.end());
        vector<pair<int, int> > e;
        for(int i = 0; i < Q; i++) e.push_back({E[i], i});
        sort(e.begin(), e.end());
        int idx = 0;
        for(int q = 0; q < Q; q++){
            int d = e[q].ff, num = e[q].ss;
            while(vv[idx].ff <= d && idx < vv.size()){
                int u = vv[idx].ss.ff, v = vv[idx].ss.ss;
                unite(u, v);
                idx++;
            }
            ans[num] = res;
        }
    }
    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:76:42: 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]
   76 |             while(vv[idx].ff <= d && idx < vv.size()){
      |                                      ~~~~^~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18