oj.uz

Submission #944395

# Submission time Handle Problem Language Result Execution time Memory
944395 2024-03-12T16:46:40 Z FucKanh Regions (IOI09_regions) C++14
100 / 100
 3987 ms 118688 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];
    }
  cout << flush;
    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:45:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         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 3 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 7 ms 8792 KB Output is correct
6 Correct 13 ms 8792 KB Output is correct
7 Correct 16 ms 8792 KB Output is correct
8 Correct 20 ms 8792 KB Output is correct
9 Correct 26 ms 9132 KB Output is correct
10 Correct 51 ms 9048 KB Output is correct
11 Correct 88 ms 9304 KB Output is correct
12 Correct 113 ms 9856 KB Output is correct
13 Correct 125 ms 9440 KB Output is correct
14 Correct 231 ms 9924 KB Output is correct
15 Correct 225 ms 12384 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1461 ms 12652 KB Output is correct
2 Correct 1714 ms 11592 KB Output is correct
3 Correct 2305 ms 14292 KB Output is correct
4 Correct 187 ms 9788 KB Output is correct
5 Correct 262 ms 11544 KB Output is correct
6 Correct 490 ms 29204 KB Output is correct
7 Correct 999 ms 32192 KB Output is correct
8 Correct 1158 ms 57864 KB Output is correct
9 Correct 1973 ms 16064 KB Output is correct
10 Correct 3635 ms 118688 KB Output is correct
11 Correct 3987 ms 15364 KB Output is correct
12 Correct 1191 ms 20300 KB Output is correct
13 Correct 1745 ms 19752 KB Output is correct
14 Correct 1930 ms 33564 KB Output is correct
15 Correct 2791 ms 25584 KB Output is correct
16 Correct 2516 ms 31104 KB Output is correct
17 Correct 2495 ms 42308 KB Output is correct