답안 #916089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916089 2024-01-25T09:23:40 Z gaga999 Regions (IOI09_regions) C++17
100 / 100
5811 ms 21928 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 = 500;
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);
      |         ~~~~~^~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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 6 ms 6744 KB Output is correct
6 Correct 11 ms 6744 KB Output is correct
7 Correct 16 ms 6744 KB Output is correct
8 Correct 17 ms 6744 KB Output is correct
9 Correct 30 ms 7000 KB Output is correct
10 Correct 69 ms 7256 KB Output is correct
11 Correct 89 ms 7512 KB Output is correct
12 Correct 108 ms 7768 KB Output is correct
13 Correct 182 ms 7616 KB Output is correct
14 Correct 235 ms 8280 KB Output is correct
15 Correct 300 ms 9176 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1008 ms 10728 KB Output is correct
2 Correct 1042 ms 10284 KB Output is correct
3 Correct 2121 ms 11728 KB Output is correct
4 Correct 245 ms 8028 KB Output is correct
5 Correct 309 ms 9104 KB Output is correct
6 Correct 1237 ms 9296 KB Output is correct
7 Correct 1878 ms 10292 KB Output is correct
8 Correct 1922 ms 12612 KB Output is correct
9 Correct 2965 ms 14924 KB Output is correct
10 Correct 5811 ms 16752 KB Output is correct
11 Correct 5415 ms 15548 KB Output is correct
12 Correct 1299 ms 17328 KB Output is correct
13 Correct 1851 ms 16780 KB Output is correct
14 Correct 2001 ms 20560 KB Output is correct
15 Correct 3426 ms 18656 KB Output is correct
16 Correct 3463 ms 18528 KB Output is correct
17 Correct 3152 ms 21928 KB Output is correct