oj.uz

Submission #1099758

# Submission time Handle Problem Language Result Execution time Memory
1099758 2024-10-12T05:11:34 Z model_code Nile (IOI24_nile) C++17
38 / 100
 89 ms 14408 KB 
// incorrect/anany_wa_always_min_only_adjacent.cpp

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()

using ll = long long;
using ii = pair<int, int>;

const int N = 2e5 + 5;
int par[N];
int mn[N];
int sz[N];
/*
    Idea if the cc size is even I get all of them
    if it's odd I get all of them except one that one is the one with minimal A[i] - B[i]

*/
int get(int i){return i == par[i] ? i : par[i] = get(par[i]);}
vector<long long>calculate_costs(vector<int>W, vector<int>A, vector<int>B, vector<int>E) {
    int n = A.size();
    int m = E.size();
    
    ///Get elements sorted in order of Weight
    vector<ii > queries;
    vector<ii > weights;

    ll cost = 0;

    for(int i = 0; i < m; i++) {
        queries.push_back(ii(E[i], i));
    }
    for(int i = 0; i < n; i++) {
        weights.push_back(ii(W[i], i));
        par[i] = i;
        mn[i] = A[i] - B[i];
        sz[i] = 1;
        cost += A[i];
    }
    sort(all(queries));
    sort(all(weights));
    vector<ll> ans(m);
    set<pair<int, ii> > edges;
    for(int i = 1; i < n; i++) {
        edges.insert(make_pair(weights[i].first-weights[i-1].first,ii(weights[i-1].second, weights[i].second))); //INCORRECT: must consider (i,i+2) as well
    }

    for(auto p : queries) {
        while(edges.size() && edges.begin()->first <= p.first) {
            int u = edges.begin()->second.first, v = edges.begin()->second.second;
            edges.erase(edges.begin());
            u = get(u);
            v = get(v);
            if(u != v) {
                if(sz[u] & 1) cost -= mn[u];
                if(sz[v] & 1) cost -= mn[v];
                sz[u] += sz[v];
                mn[u] = min(mn[u], mn[v]); //INCORRECT: always return min
                par[v] = u;
                if(sz[u] & 1) cost += mn[u];
            }
        }
        ans[p.second] = cost;
    }
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

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

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 11972 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 54 ms 11800 KB Output is correct
2 Correct 54 ms 11992 KB Output is correct
3 Correct 55 ms 11976 KB Output is correct
4 Correct 57 ms 11976 KB Output is correct
5 Correct 56 ms 11976 KB Output is correct
6 Correct 57 ms 11876 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Incorrect 3 ms 2652 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 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Incorrect 45 ms 11972 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 54 ms 11800 KB Output is correct
2 Correct 54 ms 11992 KB Output is correct
3 Correct 55 ms 11976 KB Output is correct
4 Correct 57 ms 11976 KB Output is correct
5 Correct 56 ms 11976 KB Output is correct
6 Correct 57 ms 11876 KB Output is correct
7 Correct 73 ms 14404 KB Output is correct
8 Correct 84 ms 14400 KB Output is correct
9 Correct 85 ms 14408 KB Output is correct
10 Correct 84 ms 14376 KB Output is correct
11 Correct 81 ms 14404 KB Output is correct
12 Correct 86 ms 14160 KB Output is correct
13 Correct 81 ms 14400 KB Output is correct
14 Correct 80 ms 14404 KB Output is correct
15 Correct 89 ms 14152 KB Output is correct

Subtask #7
0.0 / 18.0

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