oj.uz

Submission #1014740

# Submission time Handle Problem Language Result Execution time Memory
1014740 2024-07-05T11:57:24 Z canadavid1 Regions (IOI09_regions) C++17
35 / 100
 3875 ms 131072 KB 
#include <iostream>
#include <vector>
#include <random>
#include <array>
#include <memory>

auto rng = std::mt19937(std::random_device()());
struct treap
{
    using H = decltype(rng)::result_type;
    struct Node;
    
    const Node* n = nullptr;
    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);
    treap(const treap& o);
    void reset();
    treap& operator=(const treap& o);
    treap& operator=(treap&& o);
    ~treap();
    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;
    H pri;
    mutable int refct=0;
    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) {}
    Node(treap o, treap l,treap r) : key(o->key),val(o->val),pri(o->pri),l(l),r(r) {}
    Node(treap o, int val) : key(o->key),val(val),pri(o->pri),l(o->l),r(o->r) {}
};
template<typename... Args>
treap::Node* alloc(Args... args)
{
    return new treap::Node(args...);
}

treap::treap(const Node* n) : n(n) {n->refct++;}

void treap::reset() 
{
    if(!n) return;
    if(!--n->refct)
    {
        delete n;
    }
    n = nullptr;
}

treap& treap::operator=(const treap& o)
{
    reset();
    n = o.n;
    if(n) n->refct++;
    return *this;
}
treap& treap::operator=(treap&& o)
{
    reset();
    n = o.n;
    if(n) n->refct++;
    return *this;
}
treap::treap(const treap& o)
{
    n = o.n;
    if(n) n->refct++;
}
treap::~treap()
{
    reset();
}

std::array<treap,3> treap::split(int key) const
{
    if(!n) return {};
    if(n->key == key) return {n->l,alloc(*this,nullptr,nullptr),n->r};
    if(key < n->key)
    {
        auto[Lp,m,Rp] = n->l.split(key);
        return {Lp,m,alloc(*this,Rp,n->r)};
    }
    else
    {
        auto[Lp,m,Rp] = n->r.split(key);
        return {alloc(*this,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(*this,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(*this,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);
        j.here_up = nullptr;
    }

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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 23 ms 2392 KB Output is correct
7 Correct 24 ms 1112 KB Output is correct
8 Correct 40 ms 2136 KB Output is correct
9 Correct 163 ms 6280 KB Output is correct
10 Correct 278 ms 7248 KB Output is correct
11 Correct 546 ms 9552 KB Output is correct
12 Correct 1177 ms 18512 KB Output is correct
13 Correct 379 ms 9300 KB Output is correct
14 Correct 855 ms 13772 KB Output is correct
15 Correct 942 ms 19536 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2150 ms 25908 KB Output is correct
2 Correct 2676 ms 27896 KB Output is correct
3 Correct 3182 ms 35712 KB Output is correct
4 Correct 3875 ms 110672 KB Output is correct
5 Runtime error 1064 ms 131072 KB Execution killed with signal 9
6 Runtime error 2537 ms 131072 KB Execution killed with signal 9
7 Runtime error 1172 ms 131072 KB Execution killed with signal 9
8 Runtime error 556 ms 131072 KB Execution killed with signal 9
9 Runtime error 225 ms 131072 KB Execution killed with signal 9
10 Runtime error 192 ms 131072 KB Execution killed with signal 9
11 Runtime error 234 ms 131072 KB Execution killed with signal 9
12 Runtime error 443 ms 131072 KB Execution killed with signal 9
13 Runtime error 288 ms 131072 KB Execution killed with signal 9
14 Runtime error 377 ms 131072 KB Execution killed with signal 9
15 Runtime error 235 ms 131072 KB Execution killed with signal 9
16 Runtime error 201 ms 131072 KB Execution killed with signal 9
17 Runtime error 302 ms 131072 KB Execution killed with signal 9