oj.uz

Submission #916084

# Submission time Handle Problem Language Result Execution time Memory
916084 2024-01-25T09:14:27 Z gaga999 Regions (IOI09_regions) C++17
0 / 100
 29 ms 16172 KB 
#include <cstdio>
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stdlib.h>
#include <cstring>
#include <string.h>
#include <string>
#include <sstream>
#include <assert.h>
#include <climits>
#include <sstream>
#include <numeric>
#include <time.h>
#include <limits.h>
#include <list>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <iomanip>
#include <complex>
#include <chrono>
#include <fstream>
#include <functional>
#include <unistd.h>
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
// const int M = 998244353;

// random_device rm;
// mt19937 rg(rm());
// default_random_engine rg(rm());
// uniform_int_distribution<int> rd(INT_MIN, INT_MAX);
// uniform_real_distribution<double> rd(0, M_PI);

void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }

inline char gc()
{
    const static int SZ = 1 << 16;
    static char buf[SZ], *p1, *p2;
    if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
        return -1;
    return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (!isdigit(c))
        f ^= !(c ^ 45), c = gc();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
    f && (x = -x), rd(y...);
}

template <typename T>
void prt(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        prt(x / 10);
    putchar((x % 10) ^ 48);
}

const int N = 2e5 + 5, M = 2.6e4;
int fa[N], po[N], *a1[M], *a2[M], in[N], ou[N], bs[N], dp[N], B;
vector<int> eg[N], mb[M];

inline void cg(int p, int v)
{
    for (; p < N; p += lowbit(p))
        bs[p] += v;
}

inline int qy(int p)
{
    int res = 0;
    for (; p; p -= lowbit(p))
        res += bs[p];
    return res;
}

inline int qy(int l, int r)
{
    return qy(r) - qy(l - 1);
}

void dfs()
{
    vector<int> sk(1, 1);
    int ct = 0;
    while (!sk.empty())
    {
        if (in[sk.back()])
            ou[sk.back()] = ct, sk.pop_back();
        else
        {
            in[sk.back()] = ++ct;
            for (int v : eg[sk.back()])
                sk.pb(v);
        }
    }
}

signed main()
{
    int n, m, q, x, y;
    rd(n, m, q, po[1]), mb[po[1]].pb(1), B = sqrt(n);
    for (int i = 2; i <= n; i++)
        rd(fa[i], po[i]), eg[fa[i]].pb(i), mb[po[i]].pb(i);
    dfs();
    for (int p = 1; p <= m; p++)
    {
        if (mb[p].size() <= B)
            continue;
        a1[p] = new int[m + 1];
        a2[p] = new int[m + 1];
        fill(a1[p], a1[p] + m + 1, 0);
        fill(a2[p], a2[p] + m + 1, 0);
        for (int v : mb[p])
            dp[v]++;
        for (int i = 1; i <= n; i++)
            dp[i] += dp[fa[i]];
        for (int i = 1; i <= m; i++)
            for (int v : mb[i])
                a1[p][i] += dp[v];
        fill(dp, dp + n + 1, 0);
        for (int v : mb[p])
            dp[v]++;
        for (int i = n; i > 0; i--)
            dp[fa[i]] += dp[i];
        for (int i = 1; i <= m; i++)
            for (int v : mb[i])
                a2[p][i] += dp[v];
        fill(dp, dp + n + 1, 0);
    }
    while (q--)
    {
        rd(x, y);
        if (mb[x].size() > B)
            prt(a1[x][y]);
        else if (mb[y].size() > B)
            prt(a2[y][x]);
        else
        {
            for (int i : mb[y])
                cg(in[i], 1);
            int ans = 0;
            for (int i : mb[x])
                ans += qy(in[i], ou[i]);
            prt(ans);
            for (int i : mb[y])
                cg(in[i], -1);
        }
        cout << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:161:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  161 |         if (mb[p].size() <= B)
      |             ~~~~~~~~~~~~~^~~~
regions.cpp:187:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  187 |         if (mb[x].size() > B)
      |             ~~~~~~~~~~~~~^~~
regions.cpp:189:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  189 |         else if (mb[y].size() > B)
      |                  ~~~~~~~~~~~~~^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 6744 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
6 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
9 Execution timed out 2 ms 6740 KB Time limit exceeded (wall clock)
10 Execution timed out 2 ms 7000 KB Time limit exceeded (wall clock)
11 Execution timed out 3 ms 7256 KB Time limit exceeded (wall clock)
12 Execution timed out 3 ms 7256 KB Time limit exceeded (wall clock)
13 Execution timed out 4 ms 7328 KB Time limit exceeded (wall clock)
14 Execution timed out 4 ms 7936 KB Time limit exceeded (wall clock)
15 Execution timed out 5 ms 8280 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6 ms 9632 KB Time limit exceeded (wall clock)
2 Execution timed out 7 ms 9104 KB Time limit exceeded (wall clock)
3 Execution timed out 9 ms 10584 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 7768 KB Time limit exceeded (wall clock)
5 Execution timed out 5 ms 8200 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 8792 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 9560 KB Time limit exceeded (wall clock)
8 Execution timed out 10 ms 11104 KB Time limit exceeded (wall clock)
9 Execution timed out 20 ms 13376 KB Time limit exceeded (wall clock)
10 Execution timed out 17 ms 14580 KB Time limit exceeded (wall clock)
11 Execution timed out 27 ms 13848 KB Time limit exceeded (wall clock)
12 Execution timed out 29 ms 15104 KB Time limit exceeded (wall clock)
13 Execution timed out 28 ms 14964 KB Time limit exceeded (wall clock)
14 Execution timed out 27 ms 14588 KB Time limit exceeded (wall clock)
15 Execution timed out 26 ms 16000 KB Time limit exceeded (wall clock)
16 Execution timed out 20 ms 15924 KB Time limit exceeded (wall clock)
17 Execution timed out 21 ms 16172 KB Time limit exceeded (wall clock)