#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
vector<pii> roads;
int n, d, u, q;
constexpr int inf = 1e9 + 7;
constexpr int none = 1e9;
vector<int> h;
vector<unordered_map<int, int>> to, from;
struct Node {
Node *left = nullptr, *right = nullptr;
int l, r, mid, exists = 0, id = 0, realL, realR;
Node(int l, int r, int id) : l(l) ,r(r),id(id) ,mid((r + l) / 2) {
realL = from[id][l];
realR = from[id][r];
}
void push() {
if (r - l > 1) {
if (!left) left = new Node(l,mid,id);
if (!right) right = new Node(mid,r,id);
}
}
};
Node* ins(int x, Node* node, int newX, int id) {
if (node->r - node->l <= 1) {
Node* z = new Node(node->l,node->r,id);
z->exists = node->exists;
z->exists += newX;
return z;
}
node->push();
Node* z = new Node(node->l,node->r,id);
if (x < node->mid) {
z->left = ins(x,node->left,newX,id);
z->right = node->right;
} else {
z->right = ins(x,node->right,newX,id);
z->left = node->left;
}
z->exists = z->left->exists + z->right->exists;
return z;
}
Node* addEdge(vector<set<pii>> &g, int a, int b, vector<Node*> &lastNodes) {
pii p = {h[b],b};
if (g[a].count(p)) {
g[a].erase(p);
return ins(to[a][p.first],lastNodes[a],-1,a);
}
else {
g[a].insert(p);
return ins(to[a][p.first],lastNodes[a],true,a);
}
}
int closest(Node* node, int x) {
if (!node) return inf;
if (node->exists == 0) return inf;
if (node->r - node->l <= 1 && node->exists > 0) return abs(x - node->realL);
if (node->realL <= x && node->realR >= x) {
return min(closest(node->left, x), closest(node->right, x));
}
if (node->realL >= x && node->left && node->left->exists > 0) return closest(node->left, x);
else {
if (node->right && node->right->exists > 0)
return closest(node->right, x);
else
return closest(node->left, x);
}
}
void dfs(Node* x, vector<int> &dfsData) {
if (x == nullptr) return;
if (x->r - x->l <= 1) {
dfsData.push_back(x->realL);
return;
}
if (x->left && x->left->exists> 0) dfs(x->left,dfsData);
if (x->right && x->right->exists>0) dfs(x->right,dfsData);
}
vector<int> getDfs(Node* d) {
vector<int> ans;
dfs(d,ans);
return ans;
}
vector<map<int,Node*>> nodes;
void init(int N, int D, int H[]) {
n = N;
d = D;
h.resize(n + 1);
for (int i = 0; i < n; ++i) {
h[i] = H[i];
}
}
void curseChanges(int U, int A[], int B[]) {
vector<set<int>> ex(n);
vector<int> siz(n);
u = U;
for (int i = 0; i < u; ++i) {
int a = A[i], b = B[i];
roads.emplace_back(a,b);
ex[a].insert(h[b]);
ex[b].insert(h[a]);
}
from.resize(n);
to.resize(n);
for (int i = 0; i < n; ++i) {
int genId =0;
for (auto v : ex[i]) {
to[i][v] = genId;
from[i][genId++] = v;
}
siz[i] = genId;
to[i][inf] = genId;
from[i][genId++] = inf;
}
// Time, Node* (Upper bound time)
nodes.resize(n + 1);
vector<Node*> lastNodes(n + 1);
for (int i = 0; i < n; ++i) {
lastNodes[i] = new Node(0,siz[i],i);
nodes[i].insert({0, lastNodes[i]});
}
vector<set<pii>> g(n + 1);
for (int i = 0; i < u; ++i) {
auto [a,b] = roads[i];
lastNodes[a] = addEdge(g,a,b,lastNodes);
lastNodes[b] = addEdge(g,b,a,lastNodes);
nodes[a].insert({-i - 1, lastNodes[a]});
nodes[b].insert({-i -1, lastNodes[b]});
}
}
int question(int a, int b, int t) {
auto itB = nodes[b].lower_bound(-t);
auto itA = nodes[a].lower_bound(-t);
Node* nodeB = itB->second, *nodeA = itA->second;
if (nodeB->exists < nodeA->exists) {
swap(a,b);
swap(nodeA,nodeB);
} // A is smaller
if (nodeB->exists == 0 || nodeA->exists == 0) {
return none;
}
vector<pii> types;
auto vec1 = getDfs(nodeA), vec2 = getDfs(nodeB);
int s1 = 0, s2 = 0;
while (s1 < vec1.size() || s2 < vec2.size()) {
if (s2 >= vec2.size() || (s1 < vec1.size() && vec1[s1] <= vec2[s2])) {
types.emplace_back(vec1[s1++],1);
} else {
types.emplace_back(vec2[s2++],2);
}
}
int ans = inf;
for (int j = 0; j < types.size() - 1; ++j) {
auto [x1, t1] = types[j];
auto [x2, t2] = types[j + 1];
if (t1 != t2) ans = min(x2 - x1, ans);
}
return ans;
}
Compilation message
potion.cpp: In constructor 'Node::Node(int, int, int)':
potion.cpp:15:32: warning: 'Node::id' will be initialized after [-Wreorder]
15 | int l, r, mid, exists = 0, id = 0, realL, realR;
| ^~
potion.cpp:15:15: warning: 'int Node::mid' [-Wreorder]
15 | int l, r, mid, exists = 0, id = 0, realL, realR;
| ^~~
potion.cpp:17:5: warning: when initialized here [-Wreorder]
17 | Node(int l, int r, int id) : l(l) ,r(r),id(id) ,mid((r + l) / 2) {
| ^~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:164:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | while (s1 < vec1.size() || s2 < vec2.size()) {
| ~~~^~~~~~~~~~~~~
potion.cpp:164:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | while (s1 < vec1.size() || s2 < vec2.size()) {
| ~~~^~~~~~~~~~~~~
potion.cpp:165:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | if (s2 >= vec2.size() || (s1 < vec1.size() && vec1[s1] <= vec2[s2])) {
| ~~~^~~~~~~~~~~~~~
potion.cpp:165:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | if (s2 >= vec2.size() || (s1 < vec1.size() && vec1[s1] <= vec2[s2])) {
| ~~~^~~~~~~~~~~~~
potion.cpp:173:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for (int j = 0; j < types.size() - 1; ++j) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1880 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1880 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1880 KB |
Output is correct |
| 4 |
Correct |
74 ms |
68640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
877 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1244 ms |
190348 KB |
Output is correct |
| 2 |
Correct |
596 ms |
142848 KB |
Output is correct |
| 3 |
Correct |
949 ms |
151308 KB |
Output is correct |
| 4 |
Correct |
961 ms |
151704 KB |
Output is correct |
| 5 |
Correct |
1175 ms |
188580 KB |
Output is correct |
| 6 |
Correct |
778 ms |
151704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
16216 KB |
Output is correct |
| 2 |
Correct |
160 ms |
18120 KB |
Output is correct |
| 3 |
Correct |
144 ms |
14200 KB |
Output is correct |
| 4 |
Correct |
660 ms |
17744 KB |
Output is correct |
| 5 |
Correct |
511 ms |
17492 KB |
Output is correct |
| 6 |
Correct |
170 ms |
14928 KB |
Output is correct |
| 7 |
Correct |
531 ms |
15704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1880 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1880 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1880 KB |
Output is correct |
| 5 |
Correct |
74 ms |
68640 KB |
Output is correct |
| 6 |
Runtime error |
877 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Halted |
0 ms |
0 KB |
- |
