oj.uz

Submission #578632

# Submission time Handle Problem Language Result Execution time Memory
578632 2022-06-17T12:11:53 Z nohaxjustsoflo Regions (IOI09_regions) C++17
55 / 100
 4685 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=501;
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-=lower_bound(ls[x].begin(), ls[x].end(), in[i])-ls[x].begin();
                answ+=lower_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-=lower_bound(ls[r].begin(), ls[r].end(), in[i])-ls[r].begin();
                    answ+=lower_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 12 ms 19096 KB Output is correct
2 Correct 10 ms 19120 KB Output is correct
3 Correct 12 ms 19024 KB Output is correct
4 Correct 14 ms 19124 KB Output is correct
5 Correct 17 ms 19128 KB Output is correct
6 Correct 25 ms 19152 KB Output is correct
7 Correct 39 ms 19144 KB Output is correct
8 Correct 51 ms 19280 KB Output is correct
9 Correct 61 ms 19664 KB Output is correct
10 Correct 92 ms 19768 KB Output is correct
11 Correct 136 ms 20096 KB Output is correct
12 Correct 151 ms 20560 KB Output is correct
13 Correct 213 ms 20304 KB Output is correct
14 Correct 317 ms 21084 KB Output is correct
15 Correct 267 ms 23632 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2661 ms 24448 KB Output isn't correct
2 Incorrect 2912 ms 23416 KB Output isn't correct
3 Incorrect 3280 ms 26424 KB Output isn't correct
4 Correct 267 ms 21072 KB Output is correct
5 Correct 384 ms 22712 KB Output is correct
6 Correct 1466 ms 22644 KB Output is correct
7 Correct 1714 ms 23968 KB Output is correct
8 Correct 1338 ms 29136 KB Output is correct
9 Correct 2440 ms 30416 KB Output is correct
10 Correct 4501 ms 35468 KB Output is correct
11 Correct 4685 ms 30944 KB Output is correct
12 Incorrect 1652 ms 31752 KB Output isn't correct
13 Incorrect 1839 ms 31932 KB Output isn't correct
14 Incorrect 2397 ms 32100 KB Output isn't correct
15 Incorrect 3168 ms 36608 KB Output isn't correct
16 Incorrect 3339 ms 41544 KB Output isn't correct
17 Incorrect 3840 ms 40424 KB Output isn't correct