oj.uz

Submission #1103416

# Submission time Handle Problem Language Result Execution time Memory
1103416 2024-10-20T23:54:47 Z aaaaaarroz Nile (IOI24_nile) C++17
32 / 100
 75 ms 20252 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) {
            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

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 / 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 2 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 42 ms 13496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13504 KB Output is correct
2 Correct 38 ms 13504 KB Output is correct
3 Correct 48 ms 14784 KB Output is correct
4 Correct 46 ms 14736 KB Output is correct
5 Correct 47 ms 13504 KB Output is correct
6 Correct 51 ms 14788 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 2 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13504 KB Output is correct
2 Correct 38 ms 13504 KB Output is correct
3 Correct 48 ms 14784 KB Output is correct
4 Correct 46 ms 14736 KB Output is correct
5 Correct 47 ms 13504 KB Output is correct
6 Correct 51 ms 14788 KB Output is correct
7 Correct 68 ms 19892 KB Output is correct
8 Correct 67 ms 20252 KB Output is correct
9 Correct 71 ms 18236 KB Output is correct
10 Correct 74 ms 20212 KB Output is correct
11 Correct 71 ms 20160 KB Output is correct
12 Correct 69 ms 18368 KB Output is correct
13 Correct 71 ms 18296 KB Output is correct
14 Correct 73 ms 20000 KB Output is correct
15 Correct 75 ms 20204 KB Output is correct

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 -