oj.uz

Submission #944392

# Submission time Handle Problem Language Result Execution time Memory
944392 2024-03-12T16:41:31 Z FucKanh Regions (IOI09_regions) C++14
100 / 100
 4099 ms 118932 KB 
#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:30:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |         if(v[a[B[i]]].size()<=K) continue;
      |            ~~~~~~~~~~~~~~~~~^~~
regions.cpp:44:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         if(v[a].size()<=K){
      |            ~~~~~~~~~~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8632 KB Output is correct
4 Correct 5 ms 8620 KB Output is correct
5 Correct 6 ms 8792 KB Output is correct
6 Correct 11 ms 8792 KB Output is correct
7 Correct 15 ms 9044 KB Output is correct
8 Correct 22 ms 8792 KB Output is correct
9 Correct 29 ms 9048 KB Output is correct
10 Correct 45 ms 9048 KB Output is correct
11 Correct 88 ms 9304 KB Output is correct
12 Correct 95 ms 9664 KB Output is correct
13 Correct 131 ms 9456 KB Output is correct
14 Correct 189 ms 10064 KB Output is correct
15 Correct 227 ms 12244 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1516 ms 12736 KB Output is correct
2 Correct 1670 ms 11684 KB Output is correct
3 Correct 2389 ms 14196 KB Output is correct
4 Correct 178 ms 9788 KB Output is correct
5 Correct 275 ms 11360 KB Output is correct
6 Correct 476 ms 29188 KB Output is correct
7 Correct 1004 ms 32072 KB Output is correct
8 Correct 1198 ms 57760 KB Output is correct
9 Correct 1797 ms 16208 KB Output is correct
10 Correct 3423 ms 118932 KB Output is correct
11 Correct 4099 ms 15612 KB Output is correct
12 Correct 1168 ms 20544 KB Output is correct
13 Correct 1587 ms 20088 KB Output is correct
14 Correct 1775 ms 33576 KB Output is correct
15 Correct 2714 ms 25588 KB Output is correct
16 Correct 2369 ms 31104 KB Output is correct
17 Correct 2644 ms 42336 KB Output is correct