oj.uz

Submission #998287

# Submission time Handle Problem Language Result Execution time Memory
998287 2024-06-13T14:04:44 Z BF001 Regions (IOI09_regions) C++17
100 / 100
 3470 ms 118696 KB 
// Check sqrt decomposition CPH to understand this solution well
// Basically combined two solutions, one works well for regions with smaller size
// The other works well for regions with larger size
// Set the line between larger and smaller as sqrt(n) or so and apply the appropriate algo for best results
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
bool vis[25001];
int n,r,q,cnt=1, a[maxn], st[maxn], en[maxn], B[maxn];
unordered_map<int,int> calc[25001];
vector<int> adj[maxn], v[25001];
void dfs(int s, int p = -1)
{
    st[s] = cnt++;
    for(auto u : adj[s])
        if(u!=p) dfs(u,s);
    en[s] = cnt-1;
}

int32_t main()
{
    cin >> n >> r >> q >> a[1];
    for(int i = 2; i <= n; i++)
    {
        int x; cin >> x >> a[i];
        adj[x].push_back(i);
    }
    int K = sqrt(n);
    dfs(1); for(int i = 1; i <= n; i++) B[st[i]]=i;
    for(int i = 1; i <= n; i++) v[a[B[i]]].push_back(st[B[i]]);
    for(int i = 1; i <= n; i++)
    {
        if(vis[a[B[i]]]) continue;
        if(v[a[B[i]]].size()<=K) continue;
        vis[a[B[i]]]=true;
        int pref[n+2]{0};
        for(auto u : v[a[B[i]]])
        {
            int l = st[B[u]], r = en[B[u]];
            pref[l]++, pref[r+1]--;
        }
        for(int j = 1; j <= n; j++)
            pref[j]+=pref[j-1], calc[a[B[j]]][a[B[i]]]+=pref[j];
    }
    while(q--)
    {
        int a, b, ans = 0; cin >> a >> b;
        if(v[a].size()<=K){
            for(auto u : v[a]){
                int l = st[B[u]], r = en[B[u]];
                auto itr = upper_bound(v[b].begin(), v[b].end(), r)-v[b].begin();
                auto itr2 = upper_bound(v[b].begin(), v[b].end(), l)-v[b].begin();
                if(itr) itr--, ans+=max((int)(itr-itr2)+1, 0);
            }
        }
        else ans = calc[b][a];
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:34:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         if(v[a[B[i]]].size()<=K) continue;
      |            ~~~~~~~~~~~~~~~~~^~~
regions.cpp:48:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         if(v[a].size()<=K){
      |            ~~~~~~~~~~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 9 ms 8792 KB Output is correct
7 Correct 16 ms 8792 KB Output is correct
8 Correct 23 ms 8792 KB Output is correct
9 Correct 23 ms 9048 KB Output is correct
10 Correct 47 ms 9048 KB Output is correct
11 Correct 82 ms 9304 KB Output is correct
12 Correct 91 ms 9812 KB Output is correct
13 Correct 116 ms 9304 KB Output is correct
14 Correct 192 ms 10072 KB Output is correct
15 Correct 223 ms 12376 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1505 ms 12624 KB Output is correct
2 Correct 1771 ms 11608 KB Output is correct
3 Correct 2485 ms 14160 KB Output is correct
4 Correct 197 ms 9816 KB Output is correct
5 Correct 282 ms 11352 KB Output is correct
6 Correct 534 ms 28948 KB Output is correct
7 Correct 1111 ms 32076 KB Output is correct
8 Correct 1175 ms 57812 KB Output is correct
9 Correct 1882 ms 16208 KB Output is correct
10 Correct 3470 ms 118696 KB Output is correct
11 Correct 3053 ms 15468 KB Output is correct
12 Correct 1122 ms 20144 KB Output is correct
13 Correct 1641 ms 19788 KB Output is correct
14 Correct 1913 ms 33564 KB Output is correct
15 Correct 2734 ms 25584 KB Output is correct
16 Correct 2789 ms 31056 KB Output is correct
17 Correct 2720 ms 42432 KB Output is correct