oj.uz

Submission #524199

# Submission time Handle Problem Language Result Execution time Memory
524199 2022-02-08T18:45:19 Z keertan Regions (IOI09_regions) C++17
100 / 100
 4660 ms 118412 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 5 ms 6856 KB Output is correct
2 Correct 4 ms 6856 KB Output is correct
3 Correct 6 ms 6856 KB Output is correct
4 Correct 7 ms 7040 KB Output is correct
5 Correct 12 ms 6984 KB Output is correct
6 Correct 12 ms 7040 KB Output is correct
7 Correct 38 ms 6984 KB Output is correct
8 Correct 37 ms 6988 KB Output is correct
9 Correct 44 ms 7368 KB Output is correct
10 Correct 87 ms 7368 KB Output is correct
11 Correct 116 ms 7752 KB Output is correct
12 Correct 146 ms 8136 KB Output is correct
13 Correct 124 ms 7880 KB Output is correct
14 Correct 286 ms 8564 KB Output is correct
15 Correct 286 ms 10952 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1912 ms 11644 KB Output is correct
2 Correct 2302 ms 10544 KB Output is correct
3 Correct 2964 ms 13316 KB Output is correct
4 Correct 307 ms 8440 KB Output is correct
5 Correct 401 ms 10048 KB Output is correct
6 Correct 701 ms 27432 KB Output is correct
7 Correct 1482 ms 31164 KB Output is correct
8 Correct 1738 ms 57076 KB Output is correct
9 Correct 2708 ms 15804 KB Output is correct
10 Correct 4587 ms 118412 KB Output is correct
11 Correct 4660 ms 15456 KB Output is correct
12 Correct 1706 ms 20024 KB Output is correct
13 Correct 2196 ms 19644 KB Output is correct
14 Correct 2652 ms 33436 KB Output is correct
15 Correct 3673 ms 25444 KB Output is correct
16 Correct 3800 ms 30912 KB Output is correct
17 Correct 3447 ms 42208 KB Output is correct