oj.uz

Submission #862006

# Submission time Handle Problem Language Result Execution time Memory
862006 2023-10-17T11:12:25 Z lozergam Regions (IOI09_regions) C++17
0 / 100
 81 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("%lli%lli%lli%lli", &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("%lli%lli", &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("%lli\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: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:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%lli%lli%lli%lli", &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("%lli%lli", &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 3 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 32768 KB Time limit exceeded (wall clock)
13 Execution timed out 17 ms 36552 KB Time limit exceeded (wall clock)
14 Execution timed out 20 ms 43540 KB Time limit exceeded (wall clock)
15 Execution timed out 22 ms 54704 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 47 ms 89908 KB Time limit exceeded (wall clock)
2 Execution timed out 59 ms 94840 KB Time limit exceeded (wall clock)
3 Execution timed out 57 ms 106260 KB Time limit exceeded (wall clock)
4 Execution timed out 21 ms 43244 KB Time limit exceeded (wall clock)
5 Execution timed out 21 ms 51544 KB Time limit exceeded (wall clock)
6 Execution timed out 36 ms 65140 KB Time limit exceeded (wall clock)
7 Execution timed out 49 ms 84768 KB Time limit exceeded (wall clock)
8 Execution timed out 57 ms 119516 KB Time limit exceeded (wall clock)
9 Runtime error 73 ms 131072 KB Execution killed with signal 9
10 Runtime error 76 ms 131072 KB Execution killed with signal 9
11 Runtime error 71 ms 131072 KB Execution killed with signal 9
12 Runtime error 73 ms 131072 KB Execution killed with signal 9
13 Runtime error 65 ms 131072 KB Execution killed with signal 9
14 Runtime error 81 ms 131072 KB Execution killed with signal 9
15 Runtime error 80 ms 131072 KB Execution killed with signal 9
16 Runtime error 79 ms 131072 KB Execution killed with signal 9
17 Runtime error 78 ms 131072 KB Execution killed with signal 9