oj.uz

Submission #670516

# Submission time Handle Problem Language Result Execution time Memory
670516 2022-12-09T12:15:28 Z kirakaminski968 Regions (IOI09_regions) C++17
100 / 100
 4513 ms 118564 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 4 ms 6864 KB Output is correct
2 Correct 4 ms 6864 KB Output is correct
3 Correct 5 ms 6864 KB Output is correct
4 Correct 7 ms 6864 KB Output is correct
5 Correct 10 ms 6992 KB Output is correct
6 Correct 11 ms 6992 KB Output is correct
7 Correct 28 ms 7000 KB Output is correct
8 Correct 19 ms 6992 KB Output is correct
9 Correct 54 ms 7376 KB Output is correct
10 Correct 76 ms 7376 KB Output is correct
11 Correct 126 ms 7760 KB Output is correct
12 Correct 144 ms 8248 KB Output is correct
13 Correct 191 ms 7888 KB Output is correct
14 Correct 256 ms 8504 KB Output is correct
15 Correct 345 ms 10960 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1573 ms 11628 KB Output is correct
2 Correct 1905 ms 10512 KB Output is correct
3 Correct 2905 ms 13264 KB Output is correct
4 Correct 280 ms 8408 KB Output is correct
5 Correct 371 ms 10048 KB Output is correct
6 Correct 789 ms 27444 KB Output is correct
7 Correct 1254 ms 31080 KB Output is correct
8 Correct 1696 ms 57064 KB Output is correct
9 Correct 2161 ms 15696 KB Output is correct
10 Correct 4513 ms 118564 KB Output is correct
11 Correct 3788 ms 15380 KB Output is correct
12 Correct 1512 ms 20092 KB Output is correct
13 Correct 2049 ms 19700 KB Output is correct
14 Correct 2496 ms 33440 KB Output is correct
15 Correct 3354 ms 25452 KB Output is correct
16 Correct 3277 ms 30956 KB Output is correct
17 Correct 3057 ms 42244 KB Output is correct