oj.uz

답안 #916093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916093 2024-01-25T09:26:19 Z gaga999 Regions (IOI09_regions) C++17
85 / 100
 2047 ms 131072 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 = 150;
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 2 ms 6744 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 3 ms 6744 KB Output is correct
5 Correct 5 ms 6744 KB Output is correct
6 Correct 8 ms 6744 KB Output is correct
7 Correct 19 ms 6744 KB Output is correct
8 Correct 19 ms 6744 KB Output is correct
9 Correct 30 ms 7000 KB Output is correct
10 Correct 54 ms 7256 KB Output is correct
11 Correct 86 ms 7512 KB Output is correct
12 Correct 100 ms 7768 KB Output is correct
13 Correct 157 ms 7512 KB Output is correct
14 Correct 143 ms 8448 KB Output is correct
15 Correct 133 ms 9344 KB Output is correct

Subtask #2
70.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 449 ms 10804 KB Output is correct
2 Correct 455 ms 10356 KB Output is correct
3 Correct 754 ms 11888 KB Output is correct
4 Correct 197 ms 9872 KB Output is correct
5 Correct 278 ms 8968 KB Output is correct
6 Correct 312 ms 12656 KB Output is correct
7 Correct 587 ms 16384 KB Output is correct
8 Correct 685 ms 20204 KB Output is correct
9 Correct 1262 ms 55140 KB Output is correct
10 Runtime error 712 ms 131072 KB Execution killed with signal 9
11 Runtime error 690 ms 131072 KB Execution killed with signal 9
12 Correct 1008 ms 93724 KB Output is correct
13 Correct 1362 ms 93660 KB Output is correct
14 Correct 1432 ms 99592 KB Output is correct
15 Runtime error 736 ms 131072 KB Execution killed with signal 9
16 Correct 2047 ms 117672 KB Output is correct
17 Correct 1911 ms 101308 KB Output is correct