oj.uz

Submission #862003

# Submission time Handle Problem Language Result Execution time Memory
862003 2023-10-17T11:00:23 Z lozergam Regions (IOI09_regions) C++17
0 / 100
 91 ms 131072 KB 
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define pb push_back

ll min(ll a , ll b)
{
    if(a < b)return a;
    return b;
}

ll max(ll a , ll b)
{
    if(a > b)return a;
    return b;
}

const ll maxn = 200052, max_SQRT = 125; // la la lay lay
ll N, R, Q, H[maxn], rgnOrd[maxn >> 3], revOrd[maxn >> 3];
vector<ll> adj[maxn], rgnLst[maxn >> 3], rgnLst2[maxn >> 3];

ll timer, tin[maxn], tout[maxn];
ll tdall[max_SQRT][max_SQRT], td[maxn][max_SQRT];
void dfs(ll f)
{
    tin[f] = timer++;
    for (ll i = 0; i < min(R, max_SQRT) && revOrd[H[f]] < max_SQRT; i++)
    {
        tdall[revOrd[H[f]]][i] += td[f][i];
    }
    for (ll nf : adj[f])
    {
        for (ll i = 0; i < min(R, max_SQRT); i++)
        {
            td[nf][i] = td[f][i] + (rgnOrd[i] == H[f]);
        }
        dfs(nf);
    }
    tout[f] = timer - 1;
}

signed main()
{
    scanf("%d%d%d%d", &N, &R, &Q, &H[0]);
    rgnLst[--H[0]].push_back(0);
    for (ll i = 1, p; i < N; i++)
    {
        scanf("%d%d", &p, &H[i]);
        adj[--p].push_back(i);
        rgnLst[--H[i]].push_back(i);
    }

    iota(rgnOrd, rgnOrd + R, 0);
    sort(rgnOrd, rgnOrd + R, [&](const ll &a, const ll &b)
         { return rgnLst[a].size() > rgnLst[b].size(); });
    for (ll i = 0; i < R; i++)
    {
        revOrd[rgnOrd[i]] = i;
    }
    dfs(0);
    for (ll i = 0; i < R; i++)
    {
        for (ll j : rgnLst[i])
        {
            rgnLst2[i].push_back(tin[j]);
        }
        sort(rgnLst2[i].begin(), rgnLst2[i].end());
    }

    for (ll a, b, ans; Q--;)
    {
        scanf("%d%d", &a, &b);
        a--, b--;
        ans = 0;
        if (revOrd[a] < max_SQRT && revOrd[b] < max_SQRT)
        {
            ans = tdall[revOrd[b]][revOrd[a]];
        }
        else if (revOrd[a] < max_SQRT)
        {
            for (ll i : rgnLst[b])
            {
                ans += td[i][revOrd[a]];
            }
        }
        else
        {
            for (ll i : rgnLst[a])
            {
                ans += upper_bound(rgnLst2[b].begin(), rgnLst2[b].end(), tout[i]) - lower_bound(rgnLst2[b].begin(), rgnLst2[b].end(), tin[i]);
            }
        }
        printf("%d\n", ans);
    }
}
/*
 ZZZZZZZ     A        M     M     IIIIIII  N     N   TTTTTTTTTT  RRRRRR   EEEEEEE  EEEEEEE
      Z     A A      M M   M M       I     NN    N       TT      R     R  E        E
     Z     A   A    M   M M   M      I     N N   N       TT      R     R  E        E
    Z     AAAAAAA  M     M     M     I     N  N  N       TT      RRRRRR   EEEEEEE  EEEEEEE
   Z      A     A  M           M     I     N   N N       TT      RR       E        E
  Z       A     A  M           M     I     N    NN       TT      R R      E        E
 ZZZZZZZ  A     A  M           M  IIIIIII  N     N       TT      R  R     EEEEEEE  EEEEEEE
 */

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:45:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   45 |     scanf("%d%d%d%d", &N, &R, &Q, &H[0]);
      |            ~^         ~~
      |             |         |
      |             int*      long long int*
      |            %lld
regions.cpp:45:15: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   45 |     scanf("%d%d%d%d", &N, &R, &Q, &H[0]);
      |              ~^           ~~
      |               |           |
      |               int*        long long int*
      |              %lld
regions.cpp:45:17: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
   45 |     scanf("%d%d%d%d", &N, &R, &Q, &H[0]);
      |                ~^             ~~
      |                 |             |
      |                 int*          long long int*
      |                %lld
regions.cpp:45:19: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
   45 |     scanf("%d%d%d%d", &N, &R, &Q, &H[0]);
      |                  ~^               ~~~~~
      |                   |               |
      |                   int*            long long int*
      |                  %lld
regions.cpp:49:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   49 |         scanf("%d%d", &p, &H[i]);
      |                ~^     ~~
      |                 |     |
      |                 int*  long long int*
      |                %lld
regions.cpp:49:19: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   49 |         scanf("%d%d", &p, &H[i]);
      |                  ~^       ~~~~~
      |                   |       |
      |                   int*    long long int*
      |                  %lld
regions.cpp:73:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   73 |         scanf("%d%d", &a, &b);
      |                ~^     ~~
      |                 |     |
      |                 int*  long long int*
      |                %lld
regions.cpp:73:19: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   73 |         scanf("%d%d", &a, &b);
      |                  ~^       ~~
      |                   |       |
      |                   int*    long long int*
      |                  %lld
regions.cpp:94:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   94 |         printf("%d\n", ans);
      |                 ~^     ~~~
      |                  |     |
      |                  int   long long int
      |                 %lld
regions.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d%d%d%d", &N, &R, &Q, &H[0]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d%d", &p, &H[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 10584 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 10584 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 10584 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 10840 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 12888 KB Time limit exceeded (wall clock)
6 Execution timed out 2 ms 12888 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 12888 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 12888 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 17496 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 21592 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 27992 KB Time limit exceeded (wall clock)
12 Execution timed out 13 ms 32724 KB Time limit exceeded (wall clock)
13 Execution timed out 16 ms 36508 KB Time limit exceeded (wall clock)
14 Execution timed out 22 ms 43232 KB Time limit exceeded (wall clock)
15 Execution timed out 21 ms 54680 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 46 ms 89944 KB Time limit exceeded (wall clock)
2 Execution timed out 57 ms 94916 KB Time limit exceeded (wall clock)
3 Execution timed out 57 ms 106252 KB Time limit exceeded (wall clock)
4 Execution timed out 21 ms 43608 KB Time limit exceeded (wall clock)
5 Execution timed out 22 ms 51372 KB Time limit exceeded (wall clock)
6 Execution timed out 36 ms 65284 KB Time limit exceeded (wall clock)
7 Execution timed out 49 ms 84880 KB Time limit exceeded (wall clock)
8 Execution timed out 57 ms 119592 KB Time limit exceeded (wall clock)
9 Runtime error 73 ms 131072 KB Execution killed with signal 9
10 Runtime error 75 ms 131072 KB Execution killed with signal 9
11 Runtime error 73 ms 131072 KB Execution killed with signal 9
12 Runtime error 81 ms 131072 KB Execution killed with signal 9
13 Runtime error 70 ms 131072 KB Execution killed with signal 9
14 Runtime error 86 ms 131072 KB Execution killed with signal 9
15 Runtime error 77 ms 131072 KB Execution killed with signal 9
16 Runtime error 91 ms 131072 KB Execution killed with signal 9
17 Runtime error 82 ms 131072 KB Execution killed with signal 9