oj.uz

Submission #916095

# Submission time Handle Problem Language Result Execution time Memory
916095 2024-01-25T09:29:52 Z gaga999 Regions (IOI09_regions) C++17
100 / 100
 3130 ms 94640 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, B = 250;
int fa[N], po[N], *a1[M], *a2[M], in[N], ou[N], bs[N], dp[N];
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;
    scanf("%d%d%d%d", &n, &m, &q, &po[1]), mb[po[1]].pb(1);
    for (int i = 2; i <= n; i++)
        scanf("%d%d", &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]], a1[p][po[i]] += dp[i];
        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], a2[p][po[i]] += dp[i];
        fill(dp, dp + n + 1, 0);
    }
    while (q--)
    {
        scanf("%d%d", &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);
        }
        putchar('\n'), fflush(stdout);
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:155:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |     scanf("%d%d%d%d", &n, &m, &q, &po[1]), mb[po[1]].pb(1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         scanf("%d%d", &fa[i], &po[i]), eg[fa[i]].pb(i), mb[po[i]].pb(i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:180:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 3 ms 6744 KB Output is correct
4 Correct 4 ms 6744 KB Output is correct
5 Correct 5 ms 6744 KB Output is correct
6 Correct 8 ms 6996 KB Output is correct
7 Correct 15 ms 6744 KB Output is correct
8 Correct 21 ms 6744 KB Output is correct
9 Correct 32 ms 7000 KB Output is correct
10 Correct 66 ms 7256 KB Output is correct
11 Correct 90 ms 7512 KB Output is correct
12 Correct 101 ms 7796 KB Output is correct
13 Correct 133 ms 7512 KB Output is correct
14 Correct 245 ms 8280 KB Output is correct
15 Correct 271 ms 9188 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 10728 KB Output is correct
2 Correct 490 ms 10184 KB Output is correct
3 Correct 2084 ms 11696 KB Output is correct
4 Correct 247 ms 8032 KB Output is correct
5 Correct 299 ms 9076 KB Output is correct
6 Correct 309 ms 12676 KB Output is correct
7 Correct 590 ms 14268 KB Output is correct
8 Correct 603 ms 20484 KB Output is correct
9 Correct 1423 ms 26912 KB Output is correct
10 Correct 1651 ms 36628 KB Output is correct
11 Correct 2007 ms 94640 KB Output is correct
12 Correct 1139 ms 17332 KB Output is correct
13 Correct 1657 ms 16776 KB Output is correct
14 Correct 1657 ms 20660 KB Output is correct
15 Correct 3077 ms 18924 KB Output is correct
16 Correct 3130 ms 18572 KB Output is correct
17 Correct 2699 ms 21760 KB Output is correct