oj.uz

Submission #907803

# Submission time Handle Problem Language Result Execution time Memory
907803 2024-01-16T04:53:04 Z trMatherz Regions (IOI09_regions) C++17
100 / 100
 3911 ms 118812 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 3 ms 8792 KB Output is correct
4 Correct 4 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 10 ms 8792 KB Output is correct
7 Correct 16 ms 8948 KB Output is correct
8 Correct 18 ms 8792 KB Output is correct
9 Correct 28 ms 9048 KB Output is correct
10 Correct 45 ms 9044 KB Output is correct
11 Correct 81 ms 9304 KB Output is correct
12 Correct 93 ms 9820 KB Output is correct
13 Correct 111 ms 9480 KB Output is correct
14 Correct 188 ms 9980 KB Output is correct
15 Correct 196 ms 12376 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1448 ms 13072 KB Output is correct
2 Correct 1709 ms 11904 KB Output is correct
3 Correct 2285 ms 14336 KB Output is correct
4 Correct 202 ms 9828 KB Output is correct
5 Correct 253 ms 11352 KB Output is correct
6 Correct 524 ms 28720 KB Output is correct
7 Correct 1102 ms 32148 KB Output is correct
8 Correct 1309 ms 57852 KB Output is correct
9 Correct 1709 ms 16160 KB Output is correct
10 Correct 3911 ms 118812 KB Output is correct
11 Correct 3767 ms 15456 KB Output is correct
12 Correct 1098 ms 20212 KB Output is correct
13 Correct 1538 ms 19820 KB Output is correct
14 Correct 1713 ms 33788 KB Output is correct
15 Correct 2529 ms 25584 KB Output is correct
16 Correct 2370 ms 30884 KB Output is correct
17 Correct 2484 ms 42456 KB Output is correct