oj.uz

Submission #977995

# Submission time Handle Problem Language Result Execution time Memory
977995 2024-05-08T15:37:38 Z canadavid1 Valley (BOI19_valley) C++17
100 / 100
 369 ms 74688 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 4 ms 604 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 52284 KB Output is correct
2 Correct 299 ms 51916 KB Output is correct
3 Correct 327 ms 55528 KB Output is correct
4 Correct 365 ms 62948 KB Output is correct
5 Correct 354 ms 63020 KB Output is correct
6 Correct 369 ms 70988 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 314 ms 52284 KB Output is correct
16 Correct 299 ms 51916 KB Output is correct
17 Correct 327 ms 55528 KB Output is correct
18 Correct 365 ms 62948 KB Output is correct
19 Correct 354 ms 63020 KB Output is correct
20 Correct 369 ms 70988 KB Output is correct
21 Correct 276 ms 52396 KB Output is correct
22 Correct 274 ms 51840 KB Output is correct
23 Correct 298 ms 53124 KB Output is correct
24 Correct 301 ms 63584 KB Output is correct
25 Correct 323 ms 72180 KB Output is correct
26 Correct 269 ms 55396 KB Output is correct
27 Correct 279 ms 54836 KB Output is correct
28 Correct 327 ms 58836 KB Output is correct
29 Correct 333 ms 65748 KB Output is correct
30 Correct 325 ms 71008 KB Output is correct
31 Correct 273 ms 55328 KB Output is correct
32 Correct 297 ms 55396 KB Output is correct
33 Correct 327 ms 58376 KB Output is correct
34 Correct 345 ms 67244 KB Output is correct
35 Correct 327 ms 74688 KB Output is correct
36 Correct 338 ms 66424 KB Output is correct