oj.uz

Submission #738070

# Submission time Handle Problem Language Result Execution time Memory
738070 2023-05-08T06:51:14 Z nonono Regions (IOI09_regions) C++14
100 / 100
 4177 ms 118700 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 6952 KB Output is correct
3 Correct 5 ms 6864 KB Output is correct
4 Correct 8 ms 6964 KB Output is correct
5 Correct 8 ms 6992 KB Output is correct
6 Correct 24 ms 6992 KB Output is correct
7 Correct 27 ms 6992 KB Output is correct
8 Correct 36 ms 6992 KB Output is correct
9 Correct 57 ms 7376 KB Output is correct
10 Correct 79 ms 7492 KB Output is correct
11 Correct 138 ms 7760 KB Output is correct
12 Correct 129 ms 8144 KB Output is correct
13 Correct 158 ms 7888 KB Output is correct
14 Correct 269 ms 8556 KB Output is correct
15 Correct 314 ms 10952 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1658 ms 11648 KB Output is correct
2 Correct 1945 ms 10568 KB Output is correct
3 Correct 2943 ms 13256 KB Output is correct
4 Correct 304 ms 8528 KB Output is correct
5 Correct 324 ms 10064 KB Output is correct
6 Correct 808 ms 27668 KB Output is correct
7 Correct 1507 ms 31060 KB Output is correct
8 Correct 1693 ms 57148 KB Output is correct
9 Correct 2055 ms 15720 KB Output is correct
10 Correct 4177 ms 118700 KB Output is correct
11 Correct 4053 ms 15352 KB Output is correct
12 Correct 1579 ms 20124 KB Output is correct
13 Correct 2103 ms 19668 KB Output is correct
14 Correct 2457 ms 33440 KB Output is correct
15 Correct 3472 ms 25452 KB Output is correct
16 Correct 3992 ms 30952 KB Output is correct
17 Correct 3603 ms 42296 KB Output is correct