Submission #1103417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103417		aaaaaarroz	Nile (IOI24_nile)	C++17	82 / 100	128 ms	18352 KiB

nile

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Dsu {
    ll cnt;
    vector<ll> parent, rank, size;
    Dsu(ll N) {
        cnt = 2 * N;
        parent.resize(N);
        rank.resize(N);
        size.resize(N, 1);
        for (ll i = 0; i < N; i++) {
            parent[i] = i;
        }
    }
    bool isSameSet(ll i, ll j) {
        return findSet(i) == findSet(j);
    }
    ll findSet(ll i) { 
        if (parent[i] == i) {
            return i;
        } else {
            return parent[i] = findSet(parent[i]);
        } 
    }
    void unionSet(ll i, ll j) {
        ll x = findSet(i);
        ll y = findSet(j);
        if (x != y) {
            if((size[x]%2)==(size[y]%2)&&size[y]%2==1){
                cnt -= 2;  
            }
            if (rank[x] > rank[y]) {
                parent[y] = x;
                size[x] += size[y];
            } else if (rank[x] < rank[y]) {
                parent[x] = y;
                size[y] += size[x];
            } else {
                parent[x] = y;
                size[y] += size[x];
                rank[y]++;
            }
        }
    }
    ll res() {
        return cnt;
    }
};
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {     
    if(E.size()>10){              
        vector<pair<ll, int>> sorted_W;
        ll n = W.size();
        for (int i = 0; i < n; i++) {
            sorted_W.push_back({W[i], i});
        }
        sort(sorted_W.begin(), sorted_W.end());
        vector<int> new_A(n), new_B(n);
        for (int i = 0; i < n; i++) {
            new_A[i] = A[sorted_W[i].second];
            new_B[i] = B[sorted_W[i].second];
        }
        A = new_A;
        B = new_B;
        Dsu dsu(n);
        vector<vector<ll>> edges;
        for (ll i = 0; i < n - 1; i++) {
            edges.push_back({abs(sorted_W[i + 1].first - sorted_W[i].first), i, i + 1});
        }
        edges.push_back({INT_MAX, -1, -1});  
        sort(edges.begin(), edges.end());
        vector<pair<ll, ll>> q;
        for (ll i = 0; i < E.size(); i++) {
            q.push_back({E[i], i});
        }
        sort(q.begin(), q.end());
        vector<ll> queries(E.size());
        ll puntero = 0;
        for (auto [d, pos] : q) {
            while (edges[puntero][0] <= d && puntero < edges.size()) {
                ll u = edges[puntero][1], v = edges[puntero][2];
                if (u != -1 && v != -1 && !dsu.isSameSet(u, v)) {
                    dsu.unionSet(u, v);
                }
                puntero++;
            }
            queries[pos] = dsu.res();
        }
        return queries;
    }
    else{
        int Q = (int)E.size();
        int N=(int)W.size();
        vector<ll>ans;
        vector<tuple<int,int,int>>ordenar;
        for(int i=0;i<N;i++){
            ordenar.push_back({W[i],B[i],A[i]});
        }
        sort(ordenar.begin(),ordenar.end());
        W.clear();
        A.clear();
        B.clear();
        for(auto[w,b,a]:ordenar){
            A.push_back(a);
            B.push_back(b);
            W.push_back(w);
        }
        for(int e=0;e<Q;e++){
            int d=E[e];
            vector<ll>dp(N,LLONG_MAX);
            for(int i=0;i<N;i++){
            if(i==0){
                dp[i]=A[i];
            }
            if(i==1){
                if((W[i]-W[i-1])<=d){
                dp[i]=(B[i]+B[i-1]);
                }
                else{
                dp[i]=(dp[i-1]+A[i]);
                }
            }
            if(i>=2){
                dp[i]=((ll)A[i]+dp[i-1]);
                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)B[i-2]+(ll)A[i-1]+dp[i-3]));
                }
                else{
                    dp[i]=min(dp[i],(ll)((ll)B[i]+(ll)B[i-2]+(ll)A[i-1]));
                }
                }
            }
            }
            ans.push_back(dp[N-1]);
        }
        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:73:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (ll i = 0; i < E.size(); i++) {
      |                        ~~^~~~~~~~~~
nile.cpp:80:54: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             while (edges[puntero][0] <= d && puntero < edges.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: 15 / 15
• Subtask 7: 0 / 18