# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
796080 | NeroZein | Chess Rush (CEOI20_chessrush) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int getDis (vector<int> h1, vector<int> h2) {
if (h1.empty() || h2.empty()) {
return INF;
}
int ret = INF;
int i = 0, j = 0;
int n = h1.size(), m = h2.size();
while (i < n || j < m) {
if (i < n && (j == m || h1[i] < h2[j])) {
if (j < m) {
ret = min(ret, h2[j] - h1[i]);
}
i++;
} else {
if (i < n) {
ret = min(ret, h1[i] - h2[j]);
}
j++;
}
}
return ret;
}
const int MX_N = 1e5 + 5;
const int MX_DAYS = 1e4 + 5;
int h[MX_N];
vector<int> friends[MX_N];
void invert (int u, int v) {
auto ite = find(friends[u].begin(), friends[u].end(), v);
if (ite != friends[u].end()) {//erase
friends[u].erase(ite);
ite = find(friends[v].begin(), friends[v].end(), u);
friends[v].erase(ite);
} else {
int n = friends[u].size();
int m = friends[v].size();
bool inserted_v = false;
for (int i = 0; i < n; ++i) {
if (h[friends[u][i]] > h[v]) {
inserted_v = true;
friends[u].insert(friends[u].begin() + i, v);
}
}
if (!inserted_v) {
friends[u].push_back(v);
}
bool inserted_u = false;
for (int i = 0; i < m; ++i) {
if (h[friends[v][i]] > h[u]) {
inserted_u = true;
friends[v].insert(friends[v].begin() + i, u);
}
}
if (!inserted_u) {
friends[v].push_back(u);
}
}
}
int ppl;
void init(int N, int D, int H[]) {
ppl = N;
for (int i = 0; i < N; ++i) {
h[i] = H[i];
}
}
void curseChanges(int U, int A[], int B[]) {
for (int day = 1; day <= U; ++day) {
int u = A[day - 1], v = B[day - 1];
invert(u, v);
}
}
int question(int x, int y, int v) {
if (x == y) {
return 0;
}
vector<int> h1, h2;
for (int i : friends[x]) {
h1.push_back(h[i]);
}
for (int i : friends[y]) {
h2.push_back(h[i]);
}
return getDis(h1, h2);
}