oj.uz

Submission #578630

# Submission time Handle Problem Language Result Execution time Memory
578630 2022-06-17T12:07:49 Z nohaxjustsoflo Regions (IOI09_regions) C++17
55 / 100
 4363 ms 41536 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 11 ms 19024 KB Output is correct
2 Correct 11 ms 18996 KB Output is correct
3 Correct 11 ms 19096 KB Output is correct
4 Correct 14 ms 19024 KB Output is correct
5 Correct 17 ms 19140 KB Output is correct
6 Correct 32 ms 19200 KB Output is correct
7 Correct 35 ms 19152 KB Output is correct
8 Correct 25 ms 19280 KB Output is correct
9 Correct 57 ms 19664 KB Output is correct
10 Correct 87 ms 19664 KB Output is correct
11 Correct 144 ms 20068 KB Output is correct
12 Correct 150 ms 20600 KB Output is correct
13 Correct 198 ms 20396 KB Output is correct
14 Correct 218 ms 21076 KB Output is correct
15 Correct 278 ms 23664 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2242 ms 24448 KB Output isn't correct
2 Incorrect 2908 ms 23416 KB Output isn't correct
3 Incorrect 3274 ms 26428 KB Output isn't correct
4 Correct 303 ms 21072 KB Output is correct
5 Correct 372 ms 22700 KB Output is correct
6 Correct 1271 ms 22600 KB Output is correct
7 Correct 1832 ms 23904 KB Output is correct
8 Correct 1359 ms 29164 KB Output is correct
9 Correct 2228 ms 30420 KB Output is correct
10 Correct 4290 ms 35516 KB Output is correct
11 Correct 4363 ms 30856 KB Output is correct
12 Incorrect 1786 ms 31756 KB Output isn't correct
13 Incorrect 2222 ms 31936 KB Output isn't correct
14 Incorrect 2668 ms 32072 KB Output isn't correct
15 Incorrect 3072 ms 36608 KB Output isn't correct
16 Incorrect 2951 ms 41536 KB Output isn't correct
17 Incorrect 2994 ms 40520 KB Output isn't correct