oj.uz

답안 #702277

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
702277 2023-02-23T12:42:07 Z Cyanmond The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 262144 KB 
#include <bits/stdc++.h>

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

constexpr int BS = 1000;
int blocks;
std::vector<std::vector<std::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]);
    }
    std::vector<std::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]);
        }
    }
    if (u % BS == 0) {
        trustListBlock.push_back(trustList);
    }
}

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;
}
/*
int main() {
  int N, D, U, Q;
  std::ios::sync_with_stdio(false); std::cin.tie(NULL);
  std::cin >> N >> D >> U >> Q;

  int *F = new int[N];
  for (int i=0; i<N; i++)
    std::cin >> F[i];
  init(N, D, F);

  int *A = new int[U], *B = new int[U];
  for (int i=0; i<U; i++) {
    std::cin >> A[i] >> B[i];
  }
  curseChanges(U, A, B);

  bool correct = true;
  for (int i=0; i<Q; i++) {
    int X,Y,V,CorrectAnswer;
    std::cin >> X >> Y >> V >> CorrectAnswer;
    int YourAnswer = question(X,Y,V);
    if (YourAnswer != CorrectAnswer) {
      std::cout << "WA! Question: " << i
		<< " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
		<<  "Your answer: " << YourAnswer
                << " Correct Answer: " << CorrectAnswer << std::endl;
      correct = false;
    } else {
      std::cerr << YourAnswer << " - OK" << std::endl;
    }
  }

  if (correct) {
    std::cout << "Correct." << std::endl;
  } else std::cout << "Incorrect." << std::endl;
  return 0;
}*/

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 652 KB Output is correct
2 Correct 87 ms 680 KB Output is correct
3 Correct 94 ms 668 KB Output is correct
4 Correct 82 ms 15276 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 222 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 238 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3093 ms 12420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 91 ms 652 KB Output is correct
3 Correct 87 ms 680 KB Output is correct
4 Correct 94 ms 668 KB Output is correct
5 Correct 82 ms 15276 KB Output is correct
6 Runtime error 222 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -