oj.uz

Submission #1099775

# Submission time Handle Problem Language Result Execution time Memory
1099775 2024-10-12T05:14:56 Z model_code Nile (IOI24_nile) C++17
32 / 100
 70 ms 11208 KB 
// incorrect/hazem_wa_only_same_parity_min.cpp

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

const int INF = 1e9;

struct DSU{
    vector <int> e;
    vector <int> c;
    vector <int> mni;
    vector<array<int, 2>> mnc;
    long long tot = 0;
    DSU(int n, vector<int> c) : e(n ,-1), c(c), mnc(n), mni(n) {
        for(int i = 0; i < n; i++){
            mni[i] = i;
            mnc[i] = {INF, INF};
            mnc[i][i % 2] = c[i];
            tot += c[i];
        }
    }
    int find(int x) { return e[x]<0? x : e[x]=find(e[x]); }
    int size(int x) { return -e[find(x)]; }
    int cost(int x) {
        return mnc[x][mni[x] % 2] * (size(x) % 2);
    }
    bool join(int i ,int j){
        int x = find(i) ,y = find(j);
        if(x == y) return false;
        tot -= cost(x);
        tot -= cost(y);
        if(e[x] > e[y]) swap(x ,y);
        e[x] += e[y]; e[y] = x;
        mnc[x][0] = min(mnc[x][0], mnc[y][0]);
        mnc[x][1] = min(mnc[x][1], mnc[y][1]);
        mni[x] = min(mni[x], mni[y]);
        tot += cost(x);
        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), c(n);
    for(int i = 0; i < n; i++){
        int j = ordW[i];
        w[i] = W[j];
        c[i] = A[j] - B[j];
    }

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

    DSU d(n, c);
    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, std::vector<int>)':
nile.cpp:13:27: warning: 'DSU::mnc' will be initialized after [-Wreorder]
   13 |     vector<array<int, 2>> mnc;
      |                           ^~~
nile.cpp:12:18: warning:   'std::vector<int> DSU::mni' [-Wreorder]
   12 |     vector <int> mni;
      |                  ^~~
nile.cpp:15:5: warning:   when initialized here [-Wreorder]
   15 |     DSU(int n, vector<int> c) : e(n ,-1), c(c), mnc(n), mni(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 576 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 8640 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 43 ms 8644 KB Output is correct
2 Correct 41 ms 8644 KB Output is correct
3 Correct 55 ms 8648 KB Output is correct
4 Correct 51 ms 8644 KB Output is correct
5 Correct 51 ms 8636 KB Output is correct
6 Correct 61 ms 8488 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 576 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 576 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 43 ms 8644 KB Output is correct
2 Correct 41 ms 8644 KB Output is correct
3 Correct 55 ms 8648 KB Output is correct
4 Correct 51 ms 8644 KB Output is correct
5 Correct 51 ms 8636 KB Output is correct
6 Correct 61 ms 8488 KB Output is correct
7 Correct 69 ms 10384 KB Output is correct
8 Correct 59 ms 10440 KB Output is correct
9 Correct 70 ms 10692 KB Output is correct
10 Correct 69 ms 10948 KB Output is correct
11 Correct 68 ms 10440 KB Output is correct
12 Correct 68 ms 10440 KB Output is correct
13 Correct 68 ms 11208 KB Output is correct
14 Correct 64 ms 10436 KB Output is correct
15 Correct 69 ms 10820 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 -