oj.uz

답안 #916090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916090 2024-01-25T09:23:53 Z gaga999 Regions (IOI09_regions) C++17
100 / 100
 5335 ms 36624 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 = 300;
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]];
        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--)
    {
        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:186:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 3 ms 6744 KB Output is correct
5 Correct 6 ms 6744 KB Output is correct
6 Correct 11 ms 6744 KB Output is correct
7 Correct 21 ms 6744 KB Output is correct
8 Correct 18 ms 6744 KB Output is correct
9 Correct 33 ms 7000 KB Output is correct
10 Correct 64 ms 7256 KB Output is correct
11 Correct 95 ms 7764 KB Output is correct
12 Correct 117 ms 7748 KB Output is correct
13 Correct 158 ms 7600 KB Output is correct
14 Correct 254 ms 8156 KB Output is correct
15 Correct 309 ms 9148 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 956 ms 10712 KB Output is correct
2 Correct 1180 ms 10064 KB Output is correct
3 Correct 2389 ms 11832 KB Output is correct
4 Correct 263 ms 8024 KB Output is correct
5 Correct 290 ms 8828 KB Output is correct
6 Correct 349 ms 12700 KB Output is correct
7 Correct 754 ms 14304 KB Output is correct
8 Correct 662 ms 20208 KB Output is correct
9 Correct 2399 ms 20860 KB Output is correct
10 Correct 1839 ms 36624 KB Output is correct
11 Correct 5335 ms 34640 KB Output is correct
12 Correct 1389 ms 17328 KB Output is correct
13 Correct 1943 ms 16788 KB Output is correct
14 Correct 1858 ms 20708 KB Output is correct
15 Correct 3693 ms 18792 KB Output is correct
16 Correct 3312 ms 18616 KB Output is correct
17 Correct 3066 ms 21756 KB Output is correct