oj.uz

Submission #730725

# Submission time Handle Problem Language Result Execution time Memory
730725 2023-04-26T10:31:54 Z shadow_sami Regions (IOI09_regions) C++17
100 / 100
 4216 ms 118488 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 6920 KB Output is correct
6 Correct 24 ms 6992 KB Output is correct
7 Correct 31 ms 7056 KB Output is correct
8 Correct 36 ms 6992 KB Output is correct
9 Correct 45 ms 7376 KB Output is correct
10 Correct 80 ms 7440 KB Output is correct
11 Correct 136 ms 7788 KB Output is correct
12 Correct 128 ms 8144 KB Output is correct
13 Correct 168 ms 7844 KB Output is correct
14 Correct 184 ms 8608 KB Output is correct
15 Correct 314 ms 10900 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1801 ms 11644 KB Output is correct
2 Correct 1921 ms 10560 KB Output is correct
3 Correct 2582 ms 13304 KB Output is correct
4 Correct 249 ms 8412 KB Output is correct
5 Correct 349 ms 10096 KB Output is correct
6 Correct 785 ms 27676 KB Output is correct
7 Correct 1325 ms 31100 KB Output is correct
8 Correct 1796 ms 57032 KB Output is correct
9 Correct 2073 ms 15652 KB Output is correct
10 Correct 4216 ms 118488 KB Output is correct
11 Correct 3777 ms 15380 KB Output is correct
12 Correct 1466 ms 20040 KB Output is correct
13 Correct 2175 ms 19816 KB Output is correct
14 Correct 2618 ms 33444 KB Output is correct
15 Correct 3479 ms 25452 KB Output is correct
16 Correct 3454 ms 30864 KB Output is correct
17 Correct 3118 ms 42260 KB Output is correct