Submission #977745

#	Time	Username	Problem	Language	Result	Execution time	Memory
977745		canadavid1	Valley (BOI19_valley)	C++17	59 / 100	3029 ms	48808 KiB

valley

#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;}
};
struct Node
{
    std::set<std::pair<NodeP,i64>> c;
    NodeP p;
    i64 p_d;
    i64 dist_store_down=LARGE; // 0 <=> this is a store
    int first,last; // when doing traversal, first and last place of this node
    int height;
    Node() {}
};

std::vector<NodeP> traversal;

NodeP::NodeP(Node* p) : num(p-&nodes[0]) {}
Node& NodeP::operator*() const {return nodes[num];}
Node* NodeP::operator->() const {return &nodes[num];}

void traverse(NodeP n)
{
    traversal.push_back(n);
    n->first = traversal.size();
    for(auto[c,d] : n->c)
    {
        c->c.erase({n,d});
        c->p = n;
        c->p_d = d;
        c->height = n->height+1;
        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)>
struct sparsetable
{
    using T = NodeP;    
    std::vector<std::vector<T>> data;
    static T comb(T a,T b)
    {
        return a->height < b->height ? a : b;
    }
    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)]);
    }
} 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;
        i64 mind = R->dist_store_down;
        auto p = R;

        while(p != cut)
        {
            d+=p->p_d;
            p=p->p;
            mind = std::min(mind,p->dist_store_down+d);
        };
        result.push_back(mind);
    }
    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 constructor 'sparsetable::sparsetable(std::vector<NodeP>)':
valley.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   94 |         for(int s = 1; s < N; s<<=1)
      |                        ~~^~~
valley.cpp:98:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NodeP>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for(int i = 0; i + s < p.size(); i++)
      |                            ~~~~~~^~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41