Submission #1159324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159324		Kalashnikov	The Potion of Great Power (CEOI20_potion)	C++20	17 / 100	3100 ms	38872 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;
unordered_map<int, unordered_set<int>> trust_graph;
vector<pair<int, pair<int, int>>> trust_log; // {day, {a, b}}

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

void curseChanges(int U_, int A[], int B[]) {
    U = U_;
    for (int i = 0; i < U; i++) {
        int a = A[i], b = B[i];
        trust_changes.push_back({a, b});
        trust_log.push_back({i + 1, {a, b}}); // Запоминаем день изменения
    }
}

void rebuildTrustGraph(int day) {
    trust_graph.clear();
    for (int i = 0; i < day; i++) {
        int a = trust_changes[i].first, b = trust_changes[i].second;
        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);
        }
    }
}

int question(int X, int Y, int V) {
    rebuildTrustGraph(V); // Восстанавливаем граф на день V

    if (trust_graph[X].empty() || trust_graph[Y].empty()) return INF;

    int min_dist = INF;
    for (int x_prime : trust_graph[X]) {
        for (int y_prime : trust_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: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30