Submission #977995

#	Time	Username	Problem	Language	Result	Execution time	Memory
977995		canadavid1	Valley (BOI19_valley)	C++17	100 / 100	369 ms	74688 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;}
    //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;
    sparsetable<mincombD>* heavy;
    NodeP heavyc;
    Node() {}
};
std::ostream& operator<<(std::ostream& os,const NodeP p)
{
    os << p.num << " ";
    if(p->heavyc) os << "(" << p->heavyc << " ";
    for(auto[c,d] : p->c) if(c!=p->heavyc) os << c << " ";
    if(p->heavyc) os << ")";
    return os;
}

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));
        }
    }
    NodeP maxc;
    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;
        traverse(c);
        n->size += c->size;
        if(!maxc || c->size > maxc->size) maxc=c;
        n->dist_store_down = std::min(n->dist_store_down,c->dist_store_down+d);
        traversal.push_back(n);
    }
    n->heavyc = maxc;
    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;
void make_hld(NodeP n)
{
    std::vector<NodeP> v;
    std::vector<NodeP> o;
    while(n) 
    {
        v.push_back(n);
        for(auto[c,_] : n->c) if(c!=n->heavyc) o.push_back(c);
        n=n->heavyc;
    }
    auto sp = new sparsetable<mincombD>(v);
    for(int i = 0; i < v.size(); i++) 
    {
        v[i]->heavy = sp;
        v[i]->heavy_idx = i;
    }
    for(auto n : o) make_hld(n);
}

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);
    make_hld(e);
    // std::cout << e << "\n";
    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 = mincombD(mind,p->dist_store_down+d);
        // };
        while(p->heavy!=cut->heavy)
        {
            mind = mincombD(mind,p->heavy->query(0,p->heavy_idx+1));
            p = p->heavy->query(0,1)->p;
        }
        // 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,p->heavy->query(cut->heavy_idx,p->heavy_idx+1));
        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 'void make_hld(NodeP)':
valley.cpp:164:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NodeP>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for(int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:218:13: warning: unused variable 'd' [-Wunused-variable]
  218 |         i64 d = 0;
      |             ^
valley.cpp: In instantiation of 'sparsetable<comb>::sparsetable(std::vector<NodeP>) [with NodeP (* comb)(NodeP, NodeP) = mincombD]':
valley.cpp:163:42:   required from here
valley.cpp:135:26: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
  135 |         for(int s = 1; s < N; s<<=1)
      |                        ~~^~~
valley.cpp:139:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NodeP>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             for(int i = 0; i + s < p.size(); i++)
      |                            ~~~~~~^~~~~~~~~~
valley.cpp: In instantiation of 'sparsetable<comb>::sparsetable(std::vector<NodeP>) [with NodeP (* comb)(NodeP, NodeP) = lowHeight]':
valley.cpp:206:43:   required from here
valley.cpp:135:26: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
  135 |         for(int s = 1; s < N; s<<=1)
      |                        ~~^~~
valley.cpp:139:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NodeP>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             for(int i = 0; i + s < p.size(); i++)
      |                            ~~~~~~^~~~~~~~~~

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