oj.uz

Submission #862008

# Submission time Handle Problem Language Result Execution time Memory
862008 2023-10-17T11:18:40 Z lozergam Regions (IOI09_regions) C++14
0 / 100
 139 ms 127520 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 2 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 2 ms 11352 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 11352 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 11352 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 13912 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 15960 KB Time limit exceeded (wall clock)
11 Execution timed out 9 ms 18264 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 18 ms 27104 KB Time limit exceeded (wall clock)
15 Execution timed out 22 ms 34052 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 40 ms 50732 KB Time limit exceeded (wall clock)
2 Execution timed out 44 ms 51000 KB Time limit exceeded (wall clock)
3 Execution timed out 47 ms 60492 KB Time limit exceeded (wall clock)
4 Execution timed out 18 ms 27272 KB Time limit exceeded (wall clock)
5 Execution timed out 20 ms 31208 KB Time limit exceeded (wall clock)
6 Execution timed out 31 ms 38584 KB Time limit exceeded (wall clock)
7 Execution timed out 43 ms 47544 KB Time limit exceeded (wall clock)
8 Execution timed out 52 ms 67712 KB Time limit exceeded (wall clock)
9 Execution timed out 87 ms 91652 KB Time limit exceeded (wall clock)
10 Execution timed out 91 ms 107864 KB Time limit exceeded (wall clock)
11 Execution timed out 136 ms 113588 KB Time limit exceeded (wall clock)
12 Execution timed out 139 ms 112896 KB Time limit exceeded (wall clock)
13 Execution timed out 108 ms 113324 KB Time limit exceeded (wall clock)
14 Execution timed out 137 ms 114908 KB Time limit exceeded (wall clock)
15 Execution timed out 112 ms 120436 KB Time limit exceeded (wall clock)
16 Execution timed out 108 ms 127520 KB Time limit exceeded (wall clock)
17 Execution timed out 106 ms 126224 KB Time limit exceeded (wall clock)