oj.uz

Submission #1051906

# Submission time Handle Problem Language Result Execution time Memory
1051906 2024-08-10T10:30:23 Z Ludissey Regions (IOI09_regions) C++17
95 / 100
 1789 ms 131072 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,50);
    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 0 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 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 10 ms 856 KB Output is correct
7 Correct 17 ms 600 KB Output is correct
8 Correct 15 ms 856 KB Output is correct
9 Correct 24 ms 3672 KB Output is correct
10 Correct 49 ms 1368 KB Output is correct
11 Correct 64 ms 1992 KB Output is correct
12 Correct 88 ms 4648 KB Output is correct
13 Correct 93 ms 2392 KB Output is correct
14 Correct 119 ms 3152 KB Output is correct
15 Correct 172 ms 26832 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 14484 KB Output is correct
2 Correct 631 ms 6904 KB Output is correct
3 Correct 988 ms 27380 KB Output is correct
4 Correct 156 ms 5624 KB Output is correct
5 Correct 220 ms 20300 KB Output is correct
6 Correct 379 ms 10684 KB Output is correct
7 Correct 527 ms 13108 KB Output is correct
8 Correct 661 ms 52636 KB Output is correct
9 Correct 1214 ms 29964 KB Output is correct
10 Correct 1448 ms 77828 KB Output is correct
11 Correct 1789 ms 30872 KB Output is correct
12 Correct 767 ms 26664 KB Output is correct
13 Correct 1032 ms 33436 KB Output is correct
14 Correct 1163 ms 29944 KB Output is correct
15 Correct 1515 ms 68628 KB Output is correct
16 Runtime error 157 ms 131072 KB Execution killed with signal 9
17 Correct 1504 ms 121452 KB Output is correct