oj.uz

Submission #1099770

# Submission time Handle Problem Language Result Execution time Memory
1099770 2024-10-12T05:13:57 Z model_code Nile (IOI24_nile) C++17
38 / 100
 75 ms 9680 KB 
// incorrect/hazem_wa_always_return_min.cpp

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

const int INF = 1e9;

struct DSU{
    vector <int> e;
    vector <int> mnc;
    long long tot = 0;
    DSU(int n, vector<int> c) : e(n ,-1), mnc(c) {
        tot = accumulate(c.begin(), c.end(), 0LL);
    }
    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] * (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] = min(mnc[x], mnc[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;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 392 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 7636 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 42 ms 8136 KB Output is correct
2 Correct 41 ms 7364 KB Output is correct
3 Correct 49 ms 8136 KB Output is correct
4 Correct 47 ms 7880 KB Output is correct
5 Correct 48 ms 7368 KB Output is correct
6 Correct 50 ms 7884 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 392 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 392 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 42 ms 7636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8136 KB Output is correct
2 Correct 41 ms 7364 KB Output is correct
3 Correct 49 ms 8136 KB Output is correct
4 Correct 47 ms 7880 KB Output is correct
5 Correct 48 ms 7368 KB Output is correct
6 Correct 50 ms 7884 KB Output is correct
7 Correct 63 ms 9412 KB Output is correct
8 Correct 58 ms 9680 KB Output is correct
9 Correct 68 ms 9464 KB Output is correct
10 Correct 70 ms 9408 KB Output is correct
11 Correct 72 ms 9408 KB Output is correct
12 Correct 68 ms 9412 KB Output is correct
13 Correct 70 ms 9404 KB Output is correct
14 Correct 66 ms 9412 KB Output is correct
15 Correct 75 ms 9412 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 392 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 42 ms 7636 KB Output isn't correct
9 Halted 0 ms 0 KB -