oj.uz

Submission #1014734

# Submission time Handle Problem Language Result Execution time Memory
1014734 2024-07-05T11:34:34 Z canadavid1 Regions (IOI09_regions) C++17
8 / 100
 167 ms 131072 KB 
#include <iostream>
#include <vector>
#include <random>
#include <array>

auto rng = std::mt19937(std::random_device()());
struct treap
{
    using H = decltype(rng)::result_type;
    struct Node;
    
    const Node *n;
    operator bool() const {return n;}
    const Node &operator*() const {return *n;}
    const Node *operator->() const {return n;}
    treap(std::nullptr_t v=nullptr) : n(nullptr) {}
    treap(const Node*p) : n(p) {}
    std::array<treap,3> split(int key) const;
    treap insert(int key, int val,H pri=0) const;
    int operator[](int key) const;
    treap add(int key, int inc) const
    {
        return insert(key,operator[](key)+inc,0);
    }
};
struct treap::Node
{
    int key;
    int val;
    int size;
    H pri;
    treap l,r;
    Node() {}
    Node(int key, int val,H pri,treap l,treap r) : key(key),val(val),pri(pri),l(l),r(r),
        size(1 + (l ? l->size : 0) + (r ? r->size : 0)) {}
    Node(const Node* o, treap l,treap r) : key(o->key),val(o->val),pri(o->pri),l(l),r(r),
        size(1 + (l ? l->size : 0) + (r ? r->size : 0)) {}
    Node(const Node* o, int val) : key(o->key),val(val),pri(o->pri),l(o->l),r(o->r),
        size(o->size) {}
};
template<typename... Args>
treap::Node* alloc(Args... args)
{
    static treap::Node* arr = nullptr;
    static int i = 0;
    if(!i)
    {
        arr = new treap::Node[1024]();
        i = 1024;
    }
    i--;
    arr[i] = treap::Node(args...);
    return &arr[i];
}

std::array<treap,3> treap::split(int key) const
{
    if(!n) return {};
    if(n->key == key) return {n->l,alloc(n,nullptr,nullptr),n->r};
    if(key < n->key)
    {
        auto[Lp,m,Rp] = n->l.split(key);
        return {Lp,m,alloc(n,Rp,n->r)};
    }
    else
    {
        auto[Lp,m,Rp] = n->r.split(key);
        return {alloc(n,n->l,Lp),m,Rp};
    }
}
treap treap::insert(int key, int val,H pri) const
{
    while(!pri) pri = rng();
    if(!n) return alloc(key,val,pri,nullptr,nullptr);
    if(n->key == key)
    {
        return alloc(n,val);
    }
    if(pri > n->pri)
    {
        auto[l,m,r] = split(key);
        return alloc(key,val,pri,l,r);
    }
    auto d = n->key < key;
    treap c[2] {n->l,n->r};
    c[d] = c[d].insert(key,val,pri);
    return alloc(n,c[0],c[1]);
}
int treap::operator[](int key) const
{
    if(!n) return 0;
    if(n->key == key) return n->val;
    if(key < n->key) return n->l[key];
    else return n->r[key];
}

treap unite(treap a,treap b) // O(m log(n/m)) where m <= n are sizes
{
    if(!a) return b;
    if(!b) return a;
    if(a->pri > b->pri) std::swap(a,b);
    auto[L,m,R] = a.split(b->key);
    return alloc(b->key,b->val + (m ? m->val : 0),b->pri,
        unite(b->l,L),unite(b->r,R));
}

struct employee
{
    int par=0;
    int region;
    treap here_up;
};

int main()
{
    std::cin.tie(0)->sync_with_stdio(0);
    int N,R,Q;
    std::cin >> N >> R >> Q;
    std::vector<employee> employees(N);
    for(auto& i : employees)
    {
        if(&i!=employees.data()) std::cin >> i.par;
        std::cin >> i.region;
        i.par--;
    }
    
    for(auto& i : employees)
    {
        if(i.par >= 0)
        {
            i.here_up = employees[i.par].here_up;
        }
        i.here_up = i.here_up.add(i.region,1);
    }
    std::vector<treap> for_each(R+1);
    for(int i = employees.size()-1; i >= 0; i--)
    {
        auto& j = employees[i];
        for_each[j.region] = unite(for_each[j.region],j.here_up);
    }

    for (int _ = 0; _ < Q; _++)
    {
        int r1,r2;
        std::cin >> r1 >> r2;

        std::cout << for_each[r2][r1] << "\n" << std::flush;
    }
    
}

Compilation message

regions.cpp: In constructor 'treap::Node::Node(int, int, treap::H, treap, treap)':
regions.cpp:32:13: warning: 'treap::Node::r' will be initialized after [-Wreorder]
   32 |     treap l,r;
      |             ^
regions.cpp:30:9: warning:   'int treap::Node::size' [-Wreorder]
   30 |     int size;
      |         ^~~~
regions.cpp:34:5: warning:   when initialized here [-Wreorder]
   34 |     Node(int key, int val,H pri,treap l,treap r) : key(key),val(val),pri(pri),l(l),r(r),
      |     ^~~~
regions.cpp: In constructor 'treap::Node::Node(const treap::Node*, treap, treap)':
regions.cpp:32:13: warning: 'treap::Node::r' will be initialized after [-Wreorder]
   32 |     treap l,r;
      |             ^
regions.cpp:30:9: warning:   'int treap::Node::size' [-Wreorder]
   30 |     int size;
      |         ^~~~
regions.cpp:36:5: warning:   when initialized here [-Wreorder]
   36 |     Node(const Node* o, treap l,treap r) : key(o->key),val(o->val),pri(o->pri),l(l),r(r),
      |     ^~~~
regions.cpp: In constructor 'treap::Node::Node(const treap::Node*, int)':
regions.cpp:32:13: warning: 'treap::Node::r' will be initialized after [-Wreorder]
   32 |     treap l,r;
      |             ^
regions.cpp:30:9: warning:   'int treap::Node::size' [-Wreorder]
   30 |     int size;
      |         ^~~~
regions.cpp:38:5: warning:   when initialized here [-Wreorder]
   38 |     Node(const Node* o, int val) : key(o->key),val(val),pri(o->pri),l(o->l),r(o->r),
      |     ^~~~

Subtask #1
8.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 6 ms 2392 KB Output is correct
6 Correct 15 ms 11096 KB Output is correct
7 Correct 19 ms 10328 KB Output is correct
8 Correct 35 ms 21848 KB Output is correct
9 Runtime error 92 ms 131072 KB Execution killed with signal 9
10 Runtime error 116 ms 131072 KB Execution killed with signal 9
11 Runtime error 103 ms 131072 KB Execution killed with signal 9
12 Runtime error 91 ms 131072 KB Execution killed with signal 9
13 Runtime error 118 ms 131072 KB Execution killed with signal 9
14 Runtime error 105 ms 131072 KB Execution killed with signal 9
15 Runtime error 93 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 95 ms 131072 KB Execution killed with signal 9
2 Runtime error 103 ms 131072 KB Execution killed with signal 9
3 Runtime error 98 ms 131072 KB Execution killed with signal 9
4 Runtime error 94 ms 131072 KB Execution killed with signal 9
5 Runtime error 101 ms 131072 KB Execution killed with signal 9
6 Runtime error 107 ms 131072 KB Execution killed with signal 9
7 Runtime error 126 ms 131072 KB Execution killed with signal 9
8 Runtime error 123 ms 131072 KB Execution killed with signal 9
9 Runtime error 133 ms 131072 KB Execution killed with signal 9
10 Runtime error 119 ms 131072 KB Execution killed with signal 9
11 Runtime error 127 ms 131072 KB Execution killed with signal 9
12 Runtime error 141 ms 131072 KB Execution killed with signal 9
13 Runtime error 134 ms 131072 KB Execution killed with signal 9
14 Runtime error 159 ms 131072 KB Execution killed with signal 9
15 Runtime error 141 ms 131072 KB Execution killed with signal 9
16 Runtime error 167 ms 131072 KB Execution killed with signal 9
17 Runtime error 129 ms 131072 KB Execution killed with signal 9