Submission #978174

#	Time	Username	Problem	Language	Result	Execution time	Memory
978174		12345678	Regions (IOI09_regions)	C++17	100 / 100	3714 ms	35256 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 85 / 85