oj.uz

Submission #1051886

# Submission time Handle Problem Language Result Execution time Memory
1051886 2024-08-10T10:25:31 Z Ludissey Regions (IOI09_regions) C++17
100 / 100
 6398 ms 55148 KB 
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef
tree<
  int,
  null_type,
  less<int>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;

vector<vector<int>> child;
vector<int> parent;
vector<vector<pair<int,int>>> up;
unordered_map<int,int> conv;
vector<int> rg;
vector<vector<int>> pr;
int need;
int sq;
vector<int> tin;
vector<int> out;
int timer=0;


vector<int> setup_down(int x, vector<int> rm){
    vector<int> cv(sq);
    if(conv[rg[x]]<sq){
        up[conv[rg[x]]][conv[rg[x]]].second++;
        cv[conv[rg[x]]]++;
        up[conv[rg[x]]][conv[rg[x]]].first++;
        rm[conv[rg[x]]]++;
    }
    for (int i=0; i<sz(rm); i++)
    {
        up[conv[rg[x]]][i].first+=rm[i];
    }
    for (auto u : child[x]) {
        vector<int> v=setup_down(u,rm);
        for (int i=0; i<sq; i++)
        {
            up[conv[rg[x]]][i].second+=v[i];
            cv[i]+=v[i];
        }
    }
    return cv;
}


void setup_euler(int x){
    tin[x]=timer++;
    for (auto u : child[x]) setup_euler(u);
    out[x]=timer++;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N,R,Q; cin >> N >> R >> Q;
    child.resize(N);
    parent.resize(N);
    up.resize(R,vector<pair<int,int>>(sq));
    rg.resize(N);
    tin.resize(N);
    out.resize(N);
    pr.resize(R);
    cin >> rg[0]; rg[0]--;
    vector<pair<int,int>> cnt(R);
    pr[rg[0]].push_back(0);
    cnt[rg[0]].first++;
    for (int i = 1; i < N; i++)
    {
        cin >> parent[i] >> rg[i]; parent[i]--; rg[i]--;
        child[parent[i]].push_back(i);
        pr[rg[i]].push_back(i);
        cnt[rg[i]].first++;
    }
    for (int i = 0; i < R; i++) cnt[i].second=i;
    
    sort(all(cnt),[&](auto &aa, auto &bb){return aa>bb; });
    for (int i = 0; i < sz(cnt); i++)
    {
        conv[cnt[i].second]=i;
    }
    sq=0;
    vector<int> ep(sq);
    timer=0;
    setup_euler(0);
    timer++;
    setup_down(0,ep);
    vector<vector<int>> sortedSTART(R);
    vector<vector<int>> sortedEND(R);
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < sz(pr[i]); j++) {
            int in1=tin[pr[i][j]], out1=out[pr[i][j]];
            sortedSTART[i].push_back(in1);
            sortedEND[i].push_back(out1);
        }
        sort(all(sortedSTART[i]));
        sort(all(sortedEND[i]));
    }
    for (int i = 0; i < Q; i++)
    {
        int sm=0;
        int e1,e2; cin >> e1>>e2; e1--; e2--;
        if(conv[e1]<sq){
            sm=up[conv[e2]][conv[e1]].first;
        }else if(conv[e2]<sq) {
            sm=up[conv[e1]][conv[e2]].second;
        }else{
            int a=0;
            int b=0;
            int c=0;
            int open=0;
            while(c<sz(sortedSTART[e2])||a<sz(sortedSTART[e1])||b<sz(sortedSTART[e1])){
                int va=1e9,vb=1e9,vc=1e9;
                if(a<sz(sortedSTART[e1])) va=sortedSTART[e1][a];
                if(b<sz(sortedEND[e1])) vb=sortedEND[e1][b];
                if(c<sz(sortedSTART[e2])) vc=sortedSTART[e2][c];
                if(a<sz(sortedSTART[e1])&&va<=min(vb,vc)){
                    a++;
                    open++;
                }else if(b<sz(sortedEND[e1])&&vb<=min(va,vc)){
                    open--;
                    b++;
                }else{
                    sm+=open;
                    c++;
                }
            }
        }
        cout << sm << endl;
    }
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 7 ms 600 KB Output is correct
7 Correct 16 ms 760 KB Output is correct
8 Correct 14 ms 600 KB Output is correct
9 Correct 15 ms 1624 KB Output is correct
10 Correct 30 ms 1368 KB Output is correct
11 Correct 64 ms 1884 KB Output is correct
12 Correct 67 ms 2904 KB Output is correct
13 Correct 91 ms 2136 KB Output is correct
14 Correct 107 ms 2904 KB Output is correct
15 Correct 131 ms 10956 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3485 ms 9388 KB Output is correct
2 Correct 6394 ms 6808 KB Output is correct
3 Correct 4848 ms 14136 KB Output is correct
4 Correct 158 ms 3892 KB Output is correct
5 Correct 201 ms 8864 KB Output is correct
6 Correct 527 ms 6820 KB Output is correct
7 Correct 711 ms 8848 KB Output is correct
8 Correct 674 ms 22788 KB Output is correct
9 Correct 1123 ms 19636 KB Output is correct
10 Correct 1535 ms 35708 KB Output is correct
11 Correct 1632 ms 20696 KB Output is correct
12 Correct 3796 ms 20156 KB Output is correct
13 Correct 4937 ms 22312 KB Output is correct
14 Correct 6398 ms 21804 KB Output is correct
15 Correct 5415 ms 34864 KB Output is correct
16 Correct 6170 ms 55148 KB Output is correct
17 Correct 5530 ms 50004 KB Output is correct