oj.uz

Submission #524320

# Submission time Handle Problem Language Result Execution time Memory
524320 2022-02-09T04:14:05 Z keertan Regions (IOI09_regions) C++17
32 / 100
 4197 ms 30684 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]]);
    
    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:35:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         if(v[a].size()<=K){
      |            ~~~~~~~~~~~^~~

Subtask #1
12.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6856 KB Output isn't correct
2 Correct 4 ms 6856 KB Output is correct
3 Correct 6 ms 6856 KB Output is correct
4 Correct 6 ms 6856 KB Output is correct
5 Correct 13 ms 6984 KB Output is correct
6 Correct 22 ms 6984 KB Output is correct
7 Correct 31 ms 6984 KB Output is correct
8 Correct 41 ms 6984 KB Output is correct
9 Correct 49 ms 7368 KB Output is correct
10 Correct 96 ms 7368 KB Output is correct
11 Correct 120 ms 7752 KB Output is correct
12 Correct 155 ms 8136 KB Output is correct
13 Correct 160 ms 7880 KB Output is correct
14 Incorrect 260 ms 8408 KB Output isn't correct
15 Incorrect 316 ms 10944 KB Output isn't correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1932 ms 11748 KB Output isn't correct
2 Incorrect 1702 ms 10376 KB Output isn't correct
3 Incorrect 2991 ms 13188 KB Output isn't correct
4 Correct 301 ms 8392 KB Output is correct
5 Correct 359 ms 10052 KB Output is correct
6 Incorrect 561 ms 10244 KB Output isn't correct
7 Incorrect 1104 ms 10672 KB Output isn't correct
8 Incorrect 1052 ms 16436 KB Output isn't correct
9 Correct 2297 ms 15740 KB Output is correct
10 Incorrect 2708 ms 24016 KB Output isn't correct
11 Correct 4197 ms 15428 KB Output is correct
12 Incorrect 1606 ms 19124 KB Output isn't correct
13 Incorrect 2287 ms 19488 KB Output isn't correct
14 Incorrect 2402 ms 19432 KB Output isn't correct
15 Incorrect 3503 ms 24452 KB Output isn't correct
16 Incorrect 3349 ms 30684 KB Output isn't correct
17 Incorrect 3196 ms 28072 KB Output isn't correct