Submission #1103416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103416		aaaaaarroz	Nile (IOI24_nile)	C++17	32 / 100	75 ms	20252 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) {                   
    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;
}

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:72:22: 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]
   72 |     for (ll i = 0; i < E.size(); i++) {
      |                    ~~^~~~~~~~~~
nile.cpp:79:50: 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]
   79 |         while (edges[puntero][0] <= d && puntero < edges.size()) {
      |                                          ~~~~~~~~^~~~~~~~~~~~~~

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