oj.uz

답안 #1097293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097293 2024-10-06T18:49:21 Z DaciejMaciej Regions (IOI09_regions) C++17
0 / 100
 228 ms 114216 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;

template <class T>

using VV = vector<vector<T>>;

using VI = vector<int>;
using VVI = vector<vector<int>>;

using VL = vector<long long>;
using VVL = vector<vector<long long>>;

using VC = vector<char>;
using VVC = vector<vector<char>>;

using VB = vector<bool>;
using VVB = vector<vector<bool>>;

using VD = vector<double>;
using VVD = vector<vector<double>>;

using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using PIL = pair<int, long long>;
using PLI = pair<long long, int>;

using VPII = vector<pair<int, int>>;
using VPLL = vector<pair<long long, long long>>;

#define LINE '\n'
#define SPACE ' '
#define PB push_back
#define FOR(i, a, b) for (int i = (a); i < (int(b)); i++)
#define FORE(i, a, b) for (int i = (a); i <= (int)((b)); i++)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define sq(a) ((a) * (a))
#define sz(x) ((int)x.size())

#define fastio()                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(nullptr);                 \
    cout.tie(nullptr)
#define debug(x) cerr << #x << " = " << x << endl;

// zero indexed
template <class T>
struct SegTree
{
    const T def = 0;
    int n;
    vector<T> seg;

    SegTree(int _size) : n(_size), seg(2 * _size, def) {}

    inline T merge(T a, T b)
    {
        return max(a, b);
    }

    void update(int pos, T val)
    {
        for (seg[pos += n] = val; pos /= 2;)
        {
            seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]);
        }
    }

    T query(int l, int r) // get [l, r]
    {
        T a = def, b = def;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2)
        {
            if (l % 2)
                a = merge(a, seg[l++]);
            if (r % 2)
                b = merge(b, seg[--r]);
        }
        return merge(a, b);
    }
};

template <class T>
struct BIT
{
    int size;
    vector<T> bit;
    vector<T> arr;

    BIT(int _size) : size(_size), bit(_size + 1), arr(_size) {}

    void set(int pos, T val)
    {
        add(pos, val - arr[pos]);
    }
    void add(int pos, T val)
    {
        arr[pos] += val;

        for (pos++; pos <= size; pos += pos & -pos)
        {
            bit[pos] += val;
        }
    }
    T query(int pos)
    {
        T res = 0;
        for (pos++; pos > 0; pos -= pos & -pos)
        {
            res += bit[pos];
        }
        return res;
    }
};

const ll MOD = 1e9 + 7;

template <class T>
inline void maxi(T &a, T b)
{
    a = max(a, b);
}

template <class T>
inline void mini(T &a, T b)
{
    a = min(a, b);
}

template <class T>
inline void addi(T &a, T b)
{
    a = (a + b) % MOD;
}

template <class T>
inline void subi(T &a, T b)
{
    a = (a - b + MOD) % MOD;
}

template <class T>
inline T add(T a, T b)
{
    return (a + b) % MOD;
}

template <class T>
inline T sub(T a, T b)
{
    return (a - b + MOD) % MOD;
}

template <class T>
inline T mul(T a, T b)
{
    return ((a % MOD) * (b % MOD)) % MOD;
}

constexpr ll binpow(ll a, ll b, ll mod)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }

    return res;
}

const int INF = 1e9;

const int MAX_N = 1e5 + 3;

void solve()
{
    int n, r, q;
    cin >> n >> r >> q;
    VI region(r);
    VV<int> g(n);
    cin >> region[0];
    region[0]--;    
    FOR(i, 1, n) {
        int p, h;
        cin >> p >> h;
        p--, h--;
        g[p].PB(i);
        region[i] = h;
    }
    
    /*
    tin - in time
    tout - out time
    rtin - rtin[tin[u]] = u
    rg - for each region list of tin vecs
    */
    VI tin(n), tout(n), rtin(n);
    VV<int> rg(r);
    int t = 0;
    function<void(int)> dfs = [&](int c) -> void {
        tin[c] = ++t;
        rtin[tin[c]] = c;
        rg[region[c]].PB(tin[c]);
        for(auto v : g[c]) dfs(v);
        tout[c] = ++t;
    };
    dfs(0);

    const int BS = sqrt(n);
    VV<int> pre; // pre[id][reg] = ans for query a, b
    VI rid(r, -1); // compress regions ids
    int id = 0;

    function<void(int, int, int)> dfs2 = [&](int c, int pr, int p_size) -> void {
        if(region[c] == pr) p_size++;
        pre[rid[pr]][region[c]] += p_size;
        for(auto v : g[c]) dfs2(v, pr, p_size);
    };

    FOR(i, 0, r) {
        if(sz(rg[i]) < BS) continue;
        rid[i] = id;
        pre.PB(VI(r));
        dfs2(0, i, 0);
        id++;
    }

    FOR(i, 0, q) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if(rid[a] != -1) {
            cout << pre[rid[a]][b] << LINE;
        }
        else {
            int rs = 0;
            for(auto v : rg[a]) { // v is the in time for region a
                rs += lower_bound(ALL(rg[b]), tout[rtin[v]]) - 
                    lower_bound(ALL(rg[b]), v);
            }
            cout << rs << LINE;
        }
    }
}

int main()
{
    fastio();

    int t = 1;
    // cin >> t;

    while (t--)
        solve();
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Runtime error 0 ms 344 KB Execution killed with signal 11
3 Runtime error 0 ms 344 KB Execution killed with signal 11
4 Runtime error 1 ms 604 KB Execution killed with signal 11
5 Runtime error 0 ms 600 KB Execution killed with signal 11
6 Runtime error 1 ms 600 KB Execution killed with signal 11
7 Runtime error 1 ms 600 KB Execution killed with signal 11
8 Runtime error 1 ms 856 KB Execution killed with signal 11
9 Runtime error 1 ms 1112 KB Execution killed with signal 11
10 Runtime error 3 ms 3160 KB Execution killed with signal 11
11 Runtime error 4 ms 4632 KB Execution killed with signal 11
12 Runtime error 8 ms 6128 KB Execution killed with signal 11
13 Execution timed out 3 ms 1624 KB Time limit exceeded (wall clock)
14 Runtime error 11 ms 8536 KB Execution killed with signal 11
15 Runtime error 24 ms 23224 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 54 ms 41360 KB Execution killed with signal 11
2 Execution timed out 16 ms 4696 KB Time limit exceeded (wall clock)
3 Runtime error 44 ms 49352 KB Execution killed with signal 11
4 Runtime error 14 ms 9048 KB Execution killed with signal 11
5 Execution timed out 14 ms 4952 KB Time limit exceeded (wall clock)
6 Runtime error 26 ms 29388 KB Execution killed with signal 11
7 Runtime error 34 ms 38740 KB Execution killed with signal 11
8 Runtime error 52 ms 58232 KB Execution killed with signal 11
9 Execution timed out 23 ms 10424 KB Time limit exceeded (wall clock)
10 Execution timed out 69 ms 22268 KB Time limit exceeded (wall clock)
11 Execution timed out 29 ms 11856 KB Time limit exceeded (wall clock)
12 Runtime error 113 ms 105548 KB Execution killed with signal 11
13 Runtime error 113 ms 103884 KB Execution killed with signal 11
14 Runtime error 104 ms 113336 KB Execution killed with signal 11
15 Execution timed out 43 ms 19396 KB Time limit exceeded (wall clock)
16 Execution timed out 228 ms 36536 KB Time limit exceeded (wall clock)
17 Runtime error 121 ms 114216 KB Execution killed with signal 11