oj.uz

Submission #578628

# Submission time Handle Problem Language Result Execution time Memory
578628 2022-06-17T12:03:47 Z nohaxjustsoflo Regions (IOI09_regions) C++17
35 / 100
 5089 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=450;
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 10 ms 19024 KB Output is correct
3 Correct 12 ms 19024 KB Output is correct
4 Correct 15 ms 19024 KB Output is correct
5 Correct 17 ms 19044 KB Output is correct
6 Correct 32 ms 19152 KB Output is correct
7 Correct 27 ms 19216 KB Output is correct
8 Correct 38 ms 19152 KB Output is correct
9 Correct 45 ms 19664 KB Output is correct
10 Correct 49 ms 19664 KB Output is correct
11 Correct 124 ms 20048 KB Output is correct
12 Correct 159 ms 20560 KB Output is correct
13 Correct 181 ms 20304 KB Output is correct
14 Correct 273 ms 21008 KB Output is correct
15 Correct 250 ms 23648 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2226 ms 24452 KB Output isn't correct
2 Incorrect 2844 ms 23420 KB Output isn't correct
3 Incorrect 3286 ms 26416 KB Output isn't correct
4 Correct 271 ms 21160 KB Output is correct
5 Correct 344 ms 22688 KB Output is correct
6 Incorrect 424 ms 22740 KB Output isn't correct
7 Incorrect 1479 ms 23880 KB Output isn't correct
8 Incorrect 1329 ms 29760 KB Output isn't correct
9 Correct 2226 ms 30436 KB Output is correct
10 Incorrect 5007 ms 35704 KB Output isn't correct
11 Correct 5089 ms 30860 KB Output is correct
12 Incorrect 1409 ms 31756 KB Output isn't correct
13 Incorrect 2289 ms 31932 KB Output isn't correct
14 Incorrect 2584 ms 32020 KB Output isn't correct
15 Incorrect 2843 ms 36608 KB Output isn't correct
16 Incorrect 2845 ms 41572 KB Output isn't correct
17 Incorrect 2650 ms 40440 KB Output isn't correct