oj.uz

Submission #1052224

# Submission time Handle Problem Language Result Execution time Memory
1052224 2024-08-10T12:34:33 Z Ludissey Regions (IOI09_regions) C++17
100 / 100
 1689 ms 97600 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);
    sq=min(R,25);
    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;
    }
    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 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 8 ms 856 KB Output is correct
7 Correct 17 ms 600 KB Output is correct
8 Correct 14 ms 600 KB Output is correct
9 Correct 27 ms 2648 KB Output is correct
10 Correct 43 ms 1368 KB Output is correct
11 Correct 56 ms 1940 KB Output is correct
12 Correct 87 ms 3876 KB Output is correct
13 Correct 81 ms 2328 KB Output is correct
14 Correct 118 ms 3160 KB Output is correct
15 Correct 144 ms 19272 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 11696 KB Output is correct
2 Correct 591 ms 6880 KB Output is correct
3 Correct 1030 ms 20816 KB Output is correct
4 Correct 142 ms 4696 KB Output is correct
5 Correct 232 ms 14700 KB Output is correct
6 Correct 416 ms 8424 KB Output is correct
7 Correct 600 ms 10876 KB Output is correct
8 Correct 676 ms 37848 KB Output is correct
9 Correct 1112 ms 23652 KB Output is correct
10 Correct 1495 ms 56204 KB Output is correct
11 Correct 1689 ms 25784 KB Output is correct
12 Correct 700 ms 23408 KB Output is correct
13 Correct 857 ms 26560 KB Output is correct
14 Correct 1089 ms 25908 KB Output is correct
15 Correct 1565 ms 50608 KB Output is correct
16 Correct 1562 ms 97600 KB Output is correct
17 Correct 1499 ms 86484 KB Output is correct