oj.uz

Submission #862009

# Submission time Handle Problem Language Result Execution time Memory
862009 2023-10-17T11:19:04 Z parlimoos Regions (IOI09_regions) C++14
0 / 100
 87 ms 131072 KB 
#include <bits/stdc++.h>
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("%lli%lli", &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:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%lli%lli%lli%lli", &N, &R, &Q, &H[0]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%lli%lli", &p, &H[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         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 2 ms 12888 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 12888 KB Time limit exceeded (wall clock)
7 Execution timed out 2 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 32600 KB Time limit exceeded (wall clock)
13 Execution timed out 18 ms 36772 KB Time limit exceeded (wall clock)
14 Execution timed out 23 ms 43288 KB Time limit exceeded (wall clock)
15 Execution timed out 21 ms 54756 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 46 ms 89708 KB Time limit exceeded (wall clock)
2 Execution timed out 51 ms 94848 KB Time limit exceeded (wall clock)
3 Execution timed out 54 ms 106256 KB Time limit exceeded (wall clock)
4 Execution timed out 23 ms 43252 KB Time limit exceeded (wall clock)
5 Execution timed out 22 ms 51372 KB Time limit exceeded (wall clock)
6 Execution timed out 37 ms 65080 KB Time limit exceeded (wall clock)
7 Execution timed out 52 ms 84844 KB Time limit exceeded (wall clock)
8 Execution timed out 56 ms 119620 KB Time limit exceeded (wall clock)
9 Runtime error 77 ms 131072 KB Execution killed with signal 9
10 Runtime error 84 ms 131072 KB Execution killed with signal 9
11 Runtime error 75 ms 131072 KB Execution killed with signal 9
12 Runtime error 85 ms 131072 KB Execution killed with signal 9
13 Runtime error 64 ms 131072 KB Execution killed with signal 9
14 Runtime error 87 ms 131072 KB Execution killed with signal 9
15 Runtime error 71 ms 131072 KB Execution killed with signal 9
16 Runtime error 79 ms 131072 KB Execution killed with signal 9
17 Runtime error 80 ms 131072 KB Execution killed with signal 9