oj.uz

Submission #496716

# Submission time Handle Problem Language Result Execution time Memory
496716 2021-12-22T03:11:43 Z Dan4Life Regions (IOI09_regions) C++17
100 / 100
 4133 ms 118496 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 4 ms 6856 KB Output is correct
2 Correct 4 ms 6856 KB Output is correct
3 Correct 5 ms 6856 KB Output is correct
4 Correct 8 ms 6896 KB Output is correct
5 Correct 11 ms 6984 KB Output is correct
6 Correct 16 ms 6928 KB Output is correct
7 Correct 35 ms 6984 KB Output is correct
8 Correct 41 ms 6984 KB Output is correct
9 Correct 57 ms 7368 KB Output is correct
10 Correct 94 ms 7368 KB Output is correct
11 Correct 137 ms 7752 KB Output is correct
12 Correct 127 ms 8136 KB Output is correct
13 Correct 154 ms 7880 KB Output is correct
14 Correct 283 ms 8536 KB Output is correct
15 Correct 260 ms 10944 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1845 ms 11584 KB Output is correct
2 Correct 1722 ms 10500 KB Output is correct
3 Correct 2856 ms 13244 KB Output is correct
4 Correct 301 ms 8520 KB Output is correct
5 Correct 354 ms 10056 KB Output is correct
6 Correct 740 ms 27632 KB Output is correct
7 Correct 1355 ms 31148 KB Output is correct
8 Correct 1869 ms 57056 KB Output is correct
9 Correct 2382 ms 15688 KB Output is correct
10 Correct 4075 ms 118496 KB Output is correct
11 Correct 4133 ms 15428 KB Output is correct
12 Correct 1401 ms 20036 KB Output is correct
13 Correct 1799 ms 19648 KB Output is correct
14 Correct 2527 ms 33432 KB Output is correct
15 Correct 2773 ms 25448 KB Output is correct
16 Correct 2969 ms 30916 KB Output is correct
17 Correct 3149 ms 42236 KB Output is correct