Submission #702272

#	Time	Username	Problem	Language	Result	Execution time	Memory
702272		Cyanmond	The Potion of Great Power (CEOI20_potion)	C++17	0 / 100	672 ms	262144 KiB

potion

#include <bits/stdc++.h>

using i64 = long long;
int n, d, u;
std::vector<int> h;
std::vector<int> a, b;

constexpr int BS = 500;
int blocks;
std::vector<std::vector<std::unordered_set<int>>> trustListBlock;

constexpr int inf = 1000000000;

void init(int N, int D, int H[]) {
    n = N; 
    d = D;
    for (int i = 0; i < n; ++i) {
        h.push_back(H[i]);
    }
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    for (int i = 0; i < u; ++i) {
        a.push_back(A[i]);
        b.push_back(B[i]);
    }
    blocks = (u + BS - 1) / BS;
    std::vector<std::unordered_set<int>> trustList(n);
    for (int i = 0; i < u; ++i) {
        if (i % BS == 0) {
            trustListBlock.push_back(trustList);
        }
        if (trustList[a[i]].find(b[i]) == trustList[a[i]].end()) {
            // insert
            trustList[a[i]].insert(b[i]);
            trustList[b[i]].insert(a[i]);
        } else {
            // erase
            trustList[a[i]].erase(b[i]);
            trustList[b[i]].erase(a[i]);
        }
    }
    assert(trustListBlock.size() == blocks);
}

int question(int x, int y, int v) {
    // check
    const int l = v / BS * BS, r = v;
    auto &trustList = trustListBlock[v / BS];
    for (int i = l; i < r; ++i) {
        if (trustList[a[i]].find(b[i]) == trustList[a[i]].end()) {
            // insert
            trustList[a[i]].insert(b[i]);
            trustList[b[i]].insert(a[i]);
        } else {
            // erase
            trustList[a[i]].erase(b[i]);
            trustList[b[i]].erase(a[i]);
        }
    }
    std::vector<std::pair<int, bool>> vals;
    for (const int e : trustList[x]) {
        vals.push_back({e, true});
    }
    for (const int e : trustList[y]) {
        vals.push_back({e, false});
    }
    std::sort(vals.begin(), vals.end(), [&](const auto &a, const auto &b) {
        return h[a.first] < h[b.first];
    });
    int answer = inf;
    for (int i = 1; i < (int)vals.size(); ++i) {
        if (vals[i - 1].second != vals[i].second) {
            answer = std::min(answer, h[vals[i].first] - h[vals[i - 1].first]);
        }
    }
    for (int i = r - 1; i >= l; --i) {
        if (trustList[a[i]].find(b[i]) == trustList[a[i]].end()) {
            // insert
            trustList[a[i]].insert(b[i]);
            trustList[b[i]].insert(a[i]);
        } else {
            // erase
            trustList[a[i]].erase(b[i]);
            trustList[b[i]].erase(a[i]);
        }
    }
    return answer;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from potion.cpp:1:
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:44:34: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::unordered_set<int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     assert(trustListBlock.size() == blocks);
      |            ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30