Submission #977974

#TimeUsernameProblemLanguageResultExecution timeMemory
977974canadavid1Valley (BOI19_valley)C++17
32 / 100
377 ms67964 KiB
#include <iostream> #include <vector> #include <set> #include <cmath> #include <algorithm> #include <bit> using i64 = long long; /* Tree rooted at E escaping just ancestor problem: have range in dfs traversal for start and stop, check containment every node stores how far to store downwards (or LARGE_NUM if none) if not ancestor, escapes. Else: find closest store, but in subtree under cut can using RMQ (using sparse table) for LCA do it in O(amount of stores in subtree) per node */ #include <stdint.h> static inline uint32_t log2(const uint32_t x) { uint32_t y; asm ( "\tbsr %1, %0\n" : "=r"(y) : "r" (x) ); return y; } constexpr i64 LARGE = 1ll<<60; struct Node; struct Road { int a,b; i64 W; }; std::vector<Node> nodes; std::vector<Road> roads; struct NodeP { int num; Node& operator*() const; Node* operator->() const; NodeP(int num=0) : num(num) {} NodeP(Node*p); operator int() const {return num;} //operator bool() const {return num;} }; NodeP mincombD(NodeP a, NodeP b); template<NodeP comb(NodeP,NodeP)> struct sparsetable; struct Node { std::set<std::pair<NodeP,i64>> c; NodeP p; i64 p_d; i64 dist_store_down=LARGE; // 0 <=> this is a store i64 dist_up; int first,last; // when doing traversal, first and last place of this node int height; int size; std::vector<std::pair<NodeP,NodeP>> par; //(grand)parent, mincombD int heavy_idx; Node() {} }; std::vector<NodeP> traversal; NodeP::NodeP(Node* p) : num(p-&nodes[0]) {} Node& NodeP::operator*() const {return num ? nodes[num] : *(Node*)nullptr;} Node* NodeP::operator->() const {return num ? &nodes[num] : nullptr;} void traverse(NodeP n) { traversal.push_back(n); n->first = traversal.size(); n->size = 1; if(n->p) { n->par.emplace_back(n->p,mincombD(n,n->p)); while(n->par.back().first->par.size()>=n->par.size()) { n->par.emplace_back(n->par.back().first->par[n->par.size()-1].first, mincombD(n->par.back().second,n->par.back().first->par[n->par.size()-1].second)); } } for(auto[c,d] : n->c) { c->c.erase({n,d}); c->p = n; c->p_d = d; c->height = n->height+1; c->dist_up = n->dist_up + d; n->size += c->size; traverse(c); n->dist_store_down = std::min(n->dist_store_down,c->dist_store_down+d); traversal.push_back(n); } n->last = traversal.size(); } //template<typename T,T comb(T,T)> NodeP lowHeight(NodeP a, NodeP b) { return a->height < b->height ? a : b; } NodeP mincombD(NodeP a, NodeP b) { auto A = a->dist_store_down - a->dist_up; auto B = b->dist_store_down - b->dist_up; return A < B ? a : b; } template<NodeP comb(NodeP,NodeP)> struct sparsetable { using T = NodeP; std::vector<std::vector<T>> data; sparsetable() {} sparsetable(std::vector<T> d) { auto N = d.size(); data.push_back(std::move(d)); for(int s = 1; s < N; s<<=1) { auto& v = data.emplace_back(); const auto& p = data[data.size()-2]; for(int i = 0; i + s < p.size(); i++) { v.push_back(comb(p[i],p[i+s])); } } } T query(int l, int r) { unsigned int d = r-l; auto s = log2(d); return comb(data[s][l],data[s][r-(1<<s)]); } }; sparsetable<lowHeight> sp; NodeP LCA(NodeP a, NodeP b) { if(a->first > b->first) std::swap(a,b); return sp.query(a->first,b->first); } bool parent(NodeP a,NodeP b) // b parent of a { return b->first <= a->first && a->first <= b->last; } int main() { int N,S,Q,E; std::cin >> N >> S >> Q >> E; nodes.resize(N+1); roads.resize(N); for(auto& i : roads) { if(&i==&roads[0]) continue; std::cin >> i.a >> i.b >> i.W; nodes[i.a].c.emplace(&nodes[i.b],i.W); nodes[i.b].c.emplace(&nodes[i.a],i.W); } for(int i = 0; i < S; i++) { int C; std::cin >> C; nodes[C].dist_store_down = 0; } NodeP e = &nodes[E]; traverse(e); sp = decltype(sp)(std::move(traversal)); std::vector<i64> result; result.reserve(Q); // -1 - escaped; -2 - oo for(int i = 0; i < Q; i++) { int I,_R; std::cin >> I >> _R; auto _cut = roads[I]; NodeP cut = nodes[_cut.a].height < nodes[_cut.b].height ? &nodes[_cut.b] : &nodes[_cut.a]; // highest height NodeP R = &nodes[_R]; if(!parent(R,cut)) {result.push_back(-1);continue;} if(R->dist_store_down==0) {result.push_back(0); continue;} if(cut->dist_store_down>=LARGE) {result.push_back(-2);continue;} i64 d = 0; NodeP mind = R; auto p = R; // while(p != cut) // { // d+=p->p_d; // p=p->p; // mind = std::min(mind,p->dist_store_down+d); // }; unsigned int hd = R->height-cut->height; for(int s = log2(hd);s >= 0; s--) { if(p->par.size()<=s) continue; if(p->par[s].first->height >= cut->height) { mind = mincombD(mind,p->par[s].second); p = p->par[s].first; } } mind = mincombD(mind,cut); result.push_back(mind->dist_store_down-mind->dist_up+R->dist_up); } for(auto i : result) { if(i==-2) std::cout << "oo\n"; else if (i==-1) std::cout << "escaped\n"; else std::cout << i << "\n"; } }

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:198:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<NodeP, NodeP> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  198 |             if(p->par.size()<=s) continue;
      |                ~~~~~~~~~~~~~^~~
valley.cpp:185:13: warning: unused variable 'd' [-Wunused-variable]
  185 |         i64 d = 0;
      |             ^
valley.cpp: In instantiation of 'sparsetable<comb>::sparsetable(std::vector<NodeP>) [with NodeP (* comb)(NodeP, NodeP) = lowHeight]':
valley.cpp:173:43:   required from here
valley.cpp:122:26: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
  122 |         for(int s = 1; s < N; s<<=1)
      |                        ~~^~~
valley.cpp:126:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NodeP>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             for(int i = 0; i + s < p.size(); i++)
      |                            ~~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...