oj.uz

Submission #1099766

# Submission time Handle Problem Language Result Execution time Memory
1099766 2024-10-12T05:13:09 Z model_code Nile (IOI24_nile) C++17
32 / 100
 57 ms 7000 KB 
// incorrect/hazem_A2B1_dsu_nlogn.cpp

#include "bits/stdc++.h"
#include "nile.h"
using namespace std;

struct DSU{
    int tot;
    vector <int> e;
    DSU(int n) : e(n ,-1), tot(n) {}
    int find(int x) { return e[x]<0? x : e[x]=find(e[x]); }
    int size(int x) { return -e[find(x)]; }
    bool join(int x ,int y){
        x = find(x) ,y = find(y);
        if(x == y) return false;
        tot -= size(x) % 2;
        tot -= size(y) % 2;
        if(e[x] > e[y]) swap(x ,y);
        e[x] += e[y]; e[y] = x;
        tot += size(x) % 2;
        return true;
    }
};

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size();
    int q = E.size();

    vector<int> ordW(n);
    iota(ordW.begin() ,ordW.end() ,0);
    sort(ordW.begin() ,ordW.end() ,[&](int i ,int j){
        return W[i] < W[j];
    });
    vector <int> ordE(q);
    iota(ordE.begin() ,ordE.end() ,0);
    sort(ordE.begin() ,ordE.end() ,[&](int i ,int j){
        return E[i] < E[j];
    });
    vector<int> w(n);
    for(int i = 0; i < n; i++)
        w[i] = W[ordW[i]];

    vector<array<int, 3>> edges;
    for(int i = 0; i+1 < n; i++)
        edges.push_back({w[i+1] - w[i], i, i+1});
    sort(edges.rbegin(), edges.rend());

    DSU d(n);
    vector<long long> R(q, accumulate(B.begin(), B.end(), 0LL));
    for(int i = 0; i < q; i++){
        while(!edges.empty() && edges.back()[0] <= E[ordE[i]]){
            auto [_, x, y] = edges.back(); edges.pop_back();
            d.join(x, y);
        }
        R[ordE[i]] += d.tot;
    }
    return R;
}

Compilation message

nile.cpp: In constructor 'DSU::DSU(int)':
nile.cpp:9:18: warning: 'DSU::e' will be initialized after [-Wreorder]
    9 |     vector <int> e;
      |                  ^
nile.cpp:8:9: warning:   'int DSU::tot' [-Wreorder]
    8 |     int tot;
      |         ^~~
nile.cpp:10:5: warning:   when initialized here [-Wreorder]
   10 |     DSU(int n) : e(n ,-1), tot(n) {}
      |     ^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 348 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 27 ms 5152 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 27 ms 5076 KB Output is correct
2 Correct 36 ms 5112 KB Output is correct
3 Correct 34 ms 5072 KB Output is correct
4 Correct 33 ms 5064 KB Output is correct
5 Correct 33 ms 5148 KB Output is correct
6 Correct 36 ms 5244 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 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 348 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 27 ms 5076 KB Output is correct
2 Correct 36 ms 5112 KB Output is correct
3 Correct 34 ms 5072 KB Output is correct
4 Correct 33 ms 5064 KB Output is correct
5 Correct 33 ms 5148 KB Output is correct
6 Correct 36 ms 5244 KB Output is correct
7 Correct 47 ms 6888 KB Output is correct
8 Correct 53 ms 6856 KB Output is correct
9 Correct 55 ms 6852 KB Output is correct
10 Correct 54 ms 7000 KB Output is correct
11 Correct 52 ms 6860 KB Output is correct
12 Correct 54 ms 6924 KB Output is correct
13 Correct 53 ms 6860 KB Output is correct
14 Correct 50 ms 6856 KB Output is correct
15 Correct 57 ms 6856 KB Output is correct

Subtask #7
0.0 / 18.0

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