제출 #1002520

#제출 시각아이디문제언어결과실행 시간메모리
1002520yoav_sThe Potion of Great Power (CEOI20_potion)C++17
52 / 100
2385 ms262144 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; typedef int ll; typedef vector<ll> v; typedef vector<v> vv; typedef vector<vv> vvv; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; typedef pair<ll,ll> p; typedef vector<p> vp; typedef vector<vp> vvp; typedef vector<vvp> vvvp; typedef pair<ll, p> tri; typedef vector<tri> vtri; typedef vector<vtri> vvtri; typedef vector<vvtri> vvvtri; #define f first #define s second #define pb push_back #define eb emplace_back #define all(v) (v).begin(),(v).end() const ll INF = 1e9; const ll mod = 1e9 + 7; ll D; struct Node { Node *l, *r; bool val; ll left, right; Node() { l = r = NULL; val = left = right = 0; } Node(ll size, ll offset) { ll act = pow(2, ceil(log2(size))); left = offset; right = offset + act - 1; val = 0; if (act > 1) { l = new Node(act / 2, offset); r = new Node(act / 2, offset + act / 2); } } Node(ll size) : Node(size, 0) {} Node(Node *l, Node *r, ll val, ll left, ll right) { this->l = l; this->r = r; this->val = val; this->left = left; this->right = right; } Node(Node *l, Node *r) { this->l = l; this->r = r; this->val = l->val | r->val; this->left = l->left; this->right = r->right; } Node *update(ll index, bool val) { if (left == right) { return new Node(NULL, NULL, val, index, index); } ll mid = (left + right) / 2; Node *curL = l, *curR = r; if (index <= mid) { curL = l->update(index, val); } else { curR = r->update(index, val); } return new Node(curL, curR); } void toList(v &arr) { if (!val || arr.size() >= D) return; if (left == right) { arr.pb(left); return; } l->toList(arr); r->toList(arr); } }; ll N; v H; ll U; vv sometimesNeighbors; vp edges; vector<vector<pair<ll, Node*>>> trees; vector<map<ll, ll>> neighborShrink; map<p, v> saved; void init(int gN, int gD, int gH[]) { N = gN; D = gD; for (ll i= 0 ; i < N; i++) H.pb(gH[i]); } void curseChanges(int gU, int A[], int B[]) { U = gU; sometimesNeighbors.resize(N); for (ll i = 0; i < U; i++) { edges.eb(A[i], B[i]); sometimesNeighbors[A[i]].pb(B[i]); sometimesNeighbors[B[i]].pb(A[i]); } trees.resize(N); vvb areNeighbors(N); neighborShrink.resize(N); for (ll i = 0; i < N; i++) { sort(all(sometimesNeighbors[i])); sometimesNeighbors[i].erase(unique(all(sometimesNeighbors[i])),sometimesNeighbors[i].end()); sort(all(sometimesNeighbors[i]),[](ll i, ll j){return H[i] < H[j];}); for (ll j = 0; j < sometimesNeighbors[i].size(); j++) { neighborShrink[i][sometimesNeighbors[i][j]] = j; } trees[i].eb(0, new Node(sometimesNeighbors[i].size())); areNeighbors[i].resize(sometimesNeighbors[i].size()); } for (ll iter = 0; iter < U; iter++) { ll j1 = neighborShrink[edges[iter].f][edges[iter].s]; ll i1 = edges[iter].f; ll i2 = edges[iter].s, j2 = neighborShrink[edges[iter].s][edges[iter].f]; if (areNeighbors[i1][j1]) { areNeighbors[i1][j1] = false; areNeighbors[i2][j2] = false; trees[i1].eb(iter + 1, trees[i1].back().s->update(j1, 0)); trees[i2].eb(iter + 1, trees[i2].back().s->update(j2, 0)); } else { areNeighbors[i1][j1] = true; areNeighbors[i2][j2] = true; trees[i1].eb(iter + 1, trees[i1].back().s->update(j1, 1)); trees[i2].eb(iter + 1, trees[i2].back().s->update(j2, 1)); } } } int question(int x, int y, int time) { auto cmp = [](pair<ll, Node *> x, pair<ll, Node*> y){return x.f < y.f || (x.f == y.f && y.s == NULL);}; auto xNeighbors = (*(upper_bound(all(trees[x]), pair<ll, Node*>(time, NULL), cmp) - 1)); auto yNeighbors = (*(upper_bound(all(trees[y]), pair<ll, Node*>(time, NULL), cmp) - 1)); v xNeighborsArr, yNeighborsArr; if (saved.count(p(x, xNeighbors.f)) > 0) xNeighborsArr = saved[p(x, xNeighbors.f)]; else { xNeighbors.s->toList(xNeighborsArr); saved[p(x, xNeighbors.f)] = xNeighborsArr; } if (saved.count(p(y, yNeighbors.f)) > 0) yNeighborsArr = saved[p(y, yNeighbors.f)]; else { yNeighbors.s->toList(yNeighborsArr); saved[p(y, yNeighbors.f)] = yNeighborsArr; } short i = 0, j = 0; ll mini = INF; while (i < xNeighborsArr.size() && j < yNeighborsArr.size()) { ll iHeight = H[sometimesNeighbors[x][xNeighborsArr[i]]]; while (j < (ll)yNeighborsArr.size() - 1 && H[sometimesNeighbors[y][yNeighborsArr[j + 1]]] <= iHeight) j++; mini = min(mini, abs(iHeight - H[sometimesNeighbors[y][yNeighborsArr[j]]])); if (j < yNeighborsArr.size() - 1) mini = min(mini, abs(iHeight - H[sometimesNeighbors[y][yNeighborsArr[j + 1]]])); i++; } return mini; } /* 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; } /**/

컴파일 시 표준 에러 (stderr) 메시지

potion.cpp:229:1: warning: "/*" within comment [-Wcomment]
  229 | /**/
      |  
potion.cpp: In constructor 'Node::Node()':
potion.cpp:40:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   40 |         val = left = right = 0;
      |               ~~~~~^~~~~~~~~~~
potion.cpp: In member function 'void Node::toList(v&)':
potion.cpp:90:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   90 |         if (!val || arr.size() >= D) return;
      |                     ~~~~~~~~~~~^~~~
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:133:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for (ll j = 0; j < sometimesNeighbors[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:181:14: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     while (i < xNeighborsArr.size() && j < yNeighborsArr.size())
      |            ~~^~~~~~~~~~~~~~~~~~~~~~
potion.cpp:181:42: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     while (i < xNeighborsArr.size() && j < yNeighborsArr.size())
      |                                        ~~^~~~~~~~~~~~~~~~~~~~~~
potion.cpp:186:15: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |         if (j < yNeighborsArr.size() - 1) mini = min(mini, abs(iHeight - H[sometimesNeighbors[y][yNeighborsArr[j + 1]]]));
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...