oj.uz

Submission #1051896

# Submission time Handle Problem Language Result Execution time Memory
1051896 2024-08-10T10:28:42 Z Ludissey Regions (IOI09_regions) C++17
0 / 100
 76 ms 49072 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=50;
    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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 344 KB Execution killed with signal 11
2 Runtime error 0 ms 600 KB Execution killed with signal 11
3 Runtime error 0 ms 344 KB Execution killed with signal 11
4 Runtime error 0 ms 600 KB Execution killed with signal 11
5 Runtime error 0 ms 600 KB Execution killed with signal 11
6 Runtime error 1 ms 600 KB Execution killed with signal 11
7 Runtime error 1 ms 856 KB Execution killed with signal 11
8 Runtime error 1 ms 856 KB Execution killed with signal 11
9 Runtime error 1 ms 1624 KB Execution killed with signal 11
10 Runtime error 2 ms 2136 KB Execution killed with signal 11
11 Runtime error 5 ms 2904 KB Execution killed with signal 11
12 Runtime error 4 ms 3928 KB Execution killed with signal 11
13 Runtime error 5 ms 3672 KB Execution killed with signal 11
14 Runtime error 6 ms 4984 KB Execution killed with signal 11
15 Runtime error 15 ms 9348 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 12888 KB Execution killed with signal 11
2 Runtime error 14 ms 10976 KB Execution killed with signal 11
3 Runtime error 16 ms 16472 KB Execution killed with signal 11
4 Runtime error 7 ms 5656 KB Execution killed with signal 11
5 Runtime error 11 ms 8792 KB Execution killed with signal 11
6 Runtime error 17 ms 9616 KB Execution killed with signal 11
7 Runtime error 17 ms 13288 KB Execution killed with signal 11
8 Runtime error 22 ms 22624 KB Execution killed with signal 11
9 Runtime error 43 ms 27708 KB Execution killed with signal 11
10 Runtime error 41 ms 38340 KB Execution killed with signal 11
11 Runtime error 69 ms 31928 KB Execution killed with signal 11
12 Runtime error 76 ms 33304 KB Execution killed with signal 11
13 Runtime error 45 ms 33104 KB Execution killed with signal 11
14 Runtime error 63 ms 33872 KB Execution killed with signal 11
15 Runtime error 67 ms 41736 KB Execution killed with signal 11
16 Runtime error 55 ms 49072 KB Execution killed with signal 11
17 Runtime error 67 ms 46276 KB Execution killed with signal 11