oj.uz

Submission #863152

# Submission time Handle Problem Language Result Execution time Memory
863152 2023-10-19T17:06:11 Z vjudge1 Regions (IOI09_regions) C++17
0 / 100
 133 ms 127620 KB 
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll int
#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: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 1 ms 9048 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 9048 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 9048 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 9048 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 11352 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 11352 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 11352 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 11352 KB Time limit exceeded (wall clock)
9 Execution timed out 6 ms 13912 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 16216 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 18136 KB Time limit exceeded (wall clock)
12 Execution timed out 10 ms 20824 KB Time limit exceeded (wall clock)
13 Execution timed out 13 ms 22360 KB Time limit exceeded (wall clock)
14 Execution timed out 22 ms 26996 KB Time limit exceeded (wall clock)
15 Execution timed out 20 ms 34284 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 45 ms 50392 KB Time limit exceeded (wall clock)
2 Execution timed out 46 ms 51348 KB Time limit exceeded (wall clock)
3 Execution timed out 47 ms 60688 KB Time limit exceeded (wall clock)
4 Execution timed out 18 ms 27224 KB Time limit exceeded (wall clock)
5 Execution timed out 21 ms 31212 KB Time limit exceeded (wall clock)
6 Execution timed out 34 ms 38484 KB Time limit exceeded (wall clock)
7 Execution timed out 43 ms 47636 KB Time limit exceeded (wall clock)
8 Execution timed out 53 ms 67928 KB Time limit exceeded (wall clock)
9 Execution timed out 90 ms 91832 KB Time limit exceeded (wall clock)
10 Execution timed out 96 ms 108084 KB Time limit exceeded (wall clock)
11 Execution timed out 119 ms 113572 KB Time limit exceeded (wall clock)
12 Execution timed out 131 ms 112896 KB Time limit exceeded (wall clock)
13 Execution timed out 108 ms 113320 KB Time limit exceeded (wall clock)
14 Execution timed out 133 ms 115004 KB Time limit exceeded (wall clock)
15 Execution timed out 116 ms 120444 KB Time limit exceeded (wall clock)
16 Execution timed out 103 ms 127620 KB Time limit exceeded (wall clock)
17 Execution timed out 102 ms 125856 KB Time limit exceeded (wall clock)