oj.uz

Submission #1103415

# Submission time Handle Problem Language Result Execution time Memory
1103415 2024-10-20T23:53:25 Z aaaaaarroz Nile (IOI24_nile) C++17
0 / 100
 37 ms 13500 KB 
#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) {
            cnt -= 2;  // Restar siempre que una unión ocurra

            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});  // Para evitar problemas de índice
    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

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 13496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 13500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 13500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -