oj.uz

Submission #578633

# Submission time Handle Problem Language Result Execution time Memory
578633 2022-06-17T12:12:54 Z nohaxjustsoflo Regions (IOI09_regions) C++17
55 / 100
 4153 ms 41572 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=601;
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 10 ms 19024 KB Output is correct
2 Correct 12 ms 19024 KB Output is correct
3 Correct 13 ms 19100 KB Output is correct
4 Correct 21 ms 19024 KB Output is correct
5 Correct 17 ms 19152 KB Output is correct
6 Correct 31 ms 19112 KB Output is correct
7 Correct 45 ms 19152 KB Output is correct
8 Correct 37 ms 19280 KB Output is correct
9 Correct 58 ms 19644 KB Output is correct
10 Correct 95 ms 19660 KB Output is correct
11 Correct 86 ms 20096 KB Output is correct
12 Correct 162 ms 20556 KB Output is correct
13 Correct 242 ms 20304 KB Output is correct
14 Correct 281 ms 21072 KB Output is correct
15 Correct 308 ms 23680 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2824 ms 24460 KB Output isn't correct
2 Incorrect 3266 ms 23424 KB Output isn't correct
3 Incorrect 3190 ms 26424 KB Output isn't correct
4 Correct 316 ms 21072 KB Output is correct
5 Correct 377 ms 22796 KB Output is correct
6 Correct 1401 ms 22628 KB Output is correct
7 Correct 1884 ms 23896 KB Output is correct
8 Correct 1113 ms 29128 KB Output is correct
9 Correct 2109 ms 30428 KB Output is correct
10 Correct 4048 ms 35492 KB Output is correct
11 Correct 4153 ms 30856 KB Output is correct
12 Incorrect 1451 ms 31752 KB Output isn't correct
13 Incorrect 1819 ms 31928 KB Output isn't correct
14 Incorrect 2453 ms 32028 KB Output isn't correct
15 Incorrect 2714 ms 36612 KB Output isn't correct
16 Incorrect 2593 ms 41572 KB Output isn't correct
17 Incorrect 2707 ms 40432 KB Output isn't correct