oj.uz

Submission #578634

# Submission time Handle Problem Language Result Execution time Memory
578634 2022-06-17T12:21:00 Z nohaxjustsoflo Regions (IOI09_regions) C++17
100 / 100
 5185 ms 41544 KB 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
//mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN = 2e5+5;
const int mod = 1e9+9;
const int mxlogN = 20;
const int mxK = 26;
const ll inf = 1e18;
const int K=700;
vector<int> adj[mxN], who[mxN];
int p[mxN], h[mxN], in[mxN], out[mxN], _time=0;
vector<int> ls[mxN], rs[mxN];
void dfs(int i)
{
    who[h[i]].push_back(i);
    in[i]=_time++;
    ls[h[i]].push_back(in[i]);
    for(int j:adj[i]) dfs(j);
    out[i]=_time;
    rs[h[i]].push_back(out[i]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, r, q; cin >> n >> r >> q;
    cin >> h[1];
    for(int i=2; i<=n; i++)
    {
        cin >> p[i] >> h[i];
        adj[p[i]].push_back(i);
    }
    dfs(1);
    vector<int> big;
    for(int i=1; i<=r; i++)
    {
        sort(ls[i].begin(), ls[i].end());
        sort(rs[i].begin(), rs[i].end());
        sort(who[i].begin(), who[i].end());
        if(who[i].size()>K) big.push_back(i);
    }
    map<pair<int,int>, int> ans;
    for(int x:big)
    {
        for(int y:big)
        {
            if(x==y) continue;
            ll answ=0;
            for(int i:who[y])
            {
                answ+=upper_bound(ls[x].begin(), ls[x].end(), in[i])-ls[x].begin();
                answ-=upper_bound(rs[x].begin(), rs[x].end(), in[i])-rs[x].begin();
            }
            ans[make_pair(x,y)]=answ;
        }
    }
    while(q--)
    {
        int r, r2; cin >> r >> r2;
        if(ans.count(make_pair(r,r2))) cout << ans[make_pair(r,r2)] << "\n";
        else
        {
            ll answ=0;
            if(who[r].size()<=K)
            {
                for(int i:who[r])
                {
                    answ+=lower_bound(ls[r2].begin(),ls[r2].end(),out[i])-ls[r2].begin();
                    answ-=lower_bound(ls[r2].begin(),ls[r2].end(),in[i])-ls[r2].begin();
                }
            }
            else
            {
                for(int i:who[r2])
                {
                    answ+=upper_bound(ls[r].begin(), ls[r].end(), in[i])-ls[r].begin();
                    answ-=upper_bound(rs[r].begin(), rs[r].end(), in[i])-rs[r].begin();
                }
            }
            cout << answ << "\n";
        }
        cout.flush();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19024 KB Output is correct
2 Correct 13 ms 19076 KB Output is correct
3 Correct 12 ms 19096 KB Output is correct
4 Correct 15 ms 19024 KB Output is correct
5 Correct 19 ms 19068 KB Output is correct
6 Correct 30 ms 19192 KB Output is correct
7 Correct 39 ms 19228 KB Output is correct
8 Correct 40 ms 19180 KB Output is correct
9 Correct 32 ms 19664 KB Output is correct
10 Correct 52 ms 19704 KB Output is correct
11 Correct 137 ms 20048 KB Output is correct
12 Correct 181 ms 20688 KB Output is correct
13 Correct 115 ms 20304 KB Output is correct
14 Correct 252 ms 21072 KB Output is correct
15 Correct 291 ms 23632 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2669 ms 24448 KB Output is correct
2 Correct 3157 ms 23536 KB Output is correct
3 Correct 3311 ms 26452 KB Output is correct
4 Correct 286 ms 21116 KB Output is correct
5 Correct 419 ms 22736 KB Output is correct
6 Correct 1377 ms 22600 KB Output is correct
7 Correct 1562 ms 24008 KB Output is correct
8 Correct 1243 ms 29136 KB Output is correct
9 Correct 2333 ms 30428 KB Output is correct
10 Correct 4975 ms 35540 KB Output is correct
11 Correct 5185 ms 30852 KB Output is correct
12 Correct 1936 ms 31824 KB Output is correct
13 Correct 2569 ms 31936 KB Output is correct
14 Correct 2863 ms 32020 KB Output is correct
15 Correct 3999 ms 36612 KB Output is correct
16 Correct 3520 ms 41544 KB Output is correct
17 Correct 3162 ms 40428 KB Output is correct