oj.uz

Submission #533370

# Submission time Handle Problem Language Result Execution time Memory
533370 2022-03-05T18:19:24 Z guest35178 Regions (IOI09_regions) C++17
100 / 100
 4576 ms 118456 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 6856 KB Output is correct
2 Correct 4 ms 6856 KB Output is correct
3 Correct 5 ms 6856 KB Output is correct
4 Correct 8 ms 6856 KB Output is correct
5 Correct 10 ms 6984 KB Output is correct
6 Correct 20 ms 6984 KB Output is correct
7 Correct 33 ms 6984 KB Output is correct
8 Correct 38 ms 6984 KB Output is correct
9 Correct 42 ms 7368 KB Output is correct
10 Correct 97 ms 7392 KB Output is correct
11 Correct 136 ms 7752 KB Output is correct
12 Correct 142 ms 8208 KB Output is correct
13 Correct 155 ms 7908 KB Output is correct
14 Correct 295 ms 8592 KB Output is correct
15 Correct 324 ms 10872 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1943 ms 11612 KB Output is correct
2 Correct 1775 ms 10572 KB Output is correct
3 Correct 2587 ms 13248 KB Output is correct
4 Correct 215 ms 8460 KB Output is correct
5 Correct 424 ms 10020 KB Output is correct
6 Correct 746 ms 27424 KB Output is correct
7 Correct 1207 ms 31068 KB Output is correct
8 Correct 1790 ms 57148 KB Output is correct
9 Correct 2161 ms 15768 KB Output is correct
10 Correct 4576 ms 118456 KB Output is correct
11 Correct 4016 ms 15384 KB Output is correct
12 Correct 1351 ms 20192 KB Output is correct
13 Correct 1731 ms 19740 KB Output is correct
14 Correct 2629 ms 33432 KB Output is correct
15 Correct 3310 ms 25444 KB Output is correct
16 Correct 3115 ms 30888 KB Output is correct
17 Correct 3364 ms 42276 KB Output is correct