Submission #987296

#TimeUsernameProblemLanguageResultExecution timeMemory
987296crafticatThe Potion of Great Power (CEOI20_potion)C++17
Compilation error
0 ms0 KiB
#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<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->l); 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; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> d >> u >> q; h.resize(n + 1); vector<set<int>> ex(n); vector<int> siz(n); for (int i = 0; i < n; ++i) { cin >> h[i]; } for (int i = 0; i < u; ++i) { int a, b; cin >> a >> b; 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) vector<map<int,Node*>> nodes(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]}); } for (int i = 0; i < q; ++i) { int a,b, t; cin >> a >> b >> 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) { cout << none << endl; continue; } int ans = 1e9; for (auto x : getDfs(nodeA)) { ans = min(ans, closest(nodeB,from[a][x])); } cout << ans << endl; } return 0; }

Compilation message (stderr)

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) {
      |     ^~~~
/usr/bin/ld: /tmp/ccA8Bw8s.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccLvAHKs.o:potion.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccA8Bw8s.o: in function `main':
grader.cpp:(.text.startup+0xec): undefined reference to `init(int, int, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x184): undefined reference to `curseChanges(int, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x1d9): undefined reference to `question(int, int, int)'
collect2: error: ld returned 1 exit status