Submission #1159320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159320		Kalashnikov	The Potion of Great Power (CEOI20_potion)	C++20	0 / 100	181 ms	327680 KiB

potion

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int N, D, U;
vector<int> H;
vector<pair<int, int>> trust_changes;
vector<unordered_set<int>> trust_graph;
vector<vector<unordered_set<int>>> trust_history;

void init(int N_, int D_, int H_[]) {
    N = N_; D = D_;
    H.assign(H_, H_ + N);
    trust_graph.assign(N, {});
    trust_history.push_back(trust_graph);
}

void curseChanges(int U_, int A[], int B[]) {
    U = U_;
    trust_changes.resize(U);
    trust_history.reserve(U + 1);
    
    for (int i = 0; i < U; i++) {
        int a = A[i], b = B[i];
        trust_changes[i] = {a, b};
        if (trust_graph[a].count(b)) {
            trust_graph[a].erase(b);
            trust_graph[b].erase(a);
        } else {
            trust_graph[a].insert(b);
            trust_graph[b].insert(a);
        }
        trust_history.push_back(trust_graph);
    }
}

int question(int X, int Y, int V) {
    auto &graph = trust_history[V];
    
    if (graph[X].empty() || graph[Y].empty()) return INF;
    
    int min_dist = INF;
    for (int x_prime : graph[X]) {
        for (int y_prime : graph[Y]) {
            if (x_prime == y_prime) return 0;
            min_dist = min(min_dist, abs(H[x_prime] - H[y_prime]));
        }
    }
    return min_dist;
}

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