oj.uz

Submission #978174

# Submission time Handle Problem Language Result Execution time Memory
978174 2024-05-09T02:04:01 Z 12345678 Regions (IOI09_regions) C++17
100 / 100
 3714 ms 35256 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, k=500, kx=25005;

#define int long long

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

int n, x, q, p, t, in[nx], out[nx], r[nx], sz, a, b;
vector<int> d[nx], dp[kx], ds[kx], rv[nx];

void dfs(int u)
{
    in[u]=++t;
    ds[r[u]].push_back(in[u]);
    for (auto v:d[u]) dfs(v);
    out[u]=t;
}

void dfs2(int u, int cnt, int cur)
{
    if (r[u]==cur) cnt++;
    else dp[cur][r[u]]+=cnt;
    for (auto v:d[u]) dfs2(v, cnt, cur);
}

int32_t main()
{
    scanf("%d %d %d", &n, &sz, &q);
    scanf("%d", &x);
    r[1]=x;
    rv[x].push_back(1);
    for (int i=2; i<=n; i++) scanf("%d %d", &p, &x), d[p].push_back(i), r[i]=x, rv[x].push_back(i);
    dfs(1);
    for (int i=1; i<=sz; i++)
    {
        if (ds[i].size()>=k)
        {
            dp[i].resize(sz+1);
            dfs2(1, 0, i);
        }
    }
    while (q--)
    {
        scanf("%d %d", &a, &b);
        if (ds[a].size()>=k)
        {
            printf("%d\n", dp[a][b]);
        }
        else
        {
            int res=0;
            for (auto x:rv[a]) res+=prev(upper_bound(ds[b].begin(), ds[b].end(), out[x]))-lower_bound(ds[b].begin(), ds[b].end(), in[x])+1;
            printf("%d\n", res);
        }
        fflush(stdout);
    }
}

/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
*/

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:32:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   32 |     scanf("%d %d %d", &n, &sz, &q);
      |            ~^         ~~
      |             |         |
      |             int*      long long int*
      |            %lld
regions.cpp:32:16: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   32 |     scanf("%d %d %d", &n, &sz, &q);
      |               ~^          ~~~
      |                |          |
      |                int*       long long int*
      |               %lld
regions.cpp:32:19: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
   32 |     scanf("%d %d %d", &n, &sz, &q);
      |                  ~^            ~~
      |                   |            |
      |                   int*         long long int*
      |                  %lld
regions.cpp:33:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   33 |     scanf("%d", &x);
      |            ~^   ~~
      |             |   |
      |             |   long long int*
      |             int*
      |            %lld
regions.cpp:36:38: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   36 |     for (int i=2; i<=n; i++) scanf("%d %d", &p, &x), d[p].push_back(i), r[i]=x, rv[x].push_back(i);
      |                                     ~^      ~~
      |                                      |      |
      |                                      int*   long long int*
      |                                     %lld
regions.cpp:36:41: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   36 |     for (int i=2; i<=n; i++) scanf("%d %d", &p, &x), d[p].push_back(i), r[i]=x, rv[x].push_back(i);
      |                                        ~^       ~~
      |                                         |       |
      |                                         int*    long long int*
      |                                        %lld
regions.cpp:48:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   48 |         scanf("%d %d", &a, &b);
      |                ~^      ~~
      |                 |      |
      |                 int*   long long int*
      |                %lld
regions.cpp:48:20: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   48 |         scanf("%d %d", &a, &b);
      |                   ~^       ~~
      |                    |       |
      |                    int*    long long int*
      |                   %lld
regions.cpp:51:22: warning: format '%d' expects argument of type 'int', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wformat=]
   51 |             printf("%d\n", dp[a][b]);
      |                     ~^
      |                      |
      |                      int
      |                     %lld
regions.cpp:57:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   57 |             printf("%d\n", res);
      |                     ~^     ~~~
      |                      |     |
      |                      int   long long int
      |                     %lld
regions.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d %d %d", &n, &sz, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d", &x);
      |     ~~~~~^~~~~~~~~~
regions.cpp:36:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     for (int i=2; i<=n; i++) scanf("%d %d", &p, &x), d[p].push_back(i), r[i]=x, rv[x].push_back(i);
      |                              ~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10840 KB Output is correct
2 Correct 5 ms 10920 KB Output is correct
3 Correct 6 ms 10840 KB Output is correct
4 Correct 7 ms 10840 KB Output is correct
5 Correct 9 ms 10840 KB Output is correct
6 Correct 15 ms 11096 KB Output is correct
7 Correct 17 ms 11096 KB Output is correct
8 Correct 23 ms 11096 KB Output is correct
9 Correct 28 ms 11352 KB Output is correct
10 Correct 47 ms 11604 KB Output is correct
11 Correct 81 ms 12000 KB Output is correct
12 Correct 99 ms 12632 KB Output is correct
13 Correct 130 ms 12608 KB Output is correct
14 Correct 216 ms 13272 KB Output is correct
15 Correct 217 ms 15368 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1524 ms 17048 KB Output is correct
2 Correct 1696 ms 16376 KB Output is correct
3 Correct 2313 ms 18804 KB Output is correct
4 Correct 177 ms 13400 KB Output is correct
5 Correct 239 ms 14744 KB Output is correct
6 Correct 870 ms 15748 KB Output is correct
7 Correct 1376 ms 16356 KB Output is correct
8 Correct 1014 ms 21092 KB Output is correct
9 Correct 1822 ms 23636 KB Output is correct
10 Correct 3705 ms 27352 KB Output is correct
11 Correct 3714 ms 24896 KB Output is correct
12 Correct 1008 ms 26104 KB Output is correct
13 Correct 1506 ms 25856 KB Output is correct
14 Correct 1675 ms 29544 KB Output is correct
15 Correct 2448 ms 29180 KB Output is correct
16 Correct 2315 ms 32112 KB Output is correct
17 Correct 2302 ms 35256 KB Output is correct