oj.uz

Submission #1051793

# Submission time Handle Problem Language Result Execution time Memory
1051793 2024-08-10T09:47:49 Z Ludissey Regions (IOI09_regions) C++17
45 / 100
 8000 ms 123868 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> cv(sq);
    for (auto u : child[x]) {
        vector<int> v=setup_down(u);
        for (int i=0; i<sq; i++)
        {
            up[conv[rg[x]]][i].second+=v[i];
            cv[i]+=v[i];
        }
    }
    if(conv[rg[x]]<sq){
        up[conv[rg[x]]][conv[rg[x]]].second++;
        cv[conv[rg[x]]]++;
    }
    return cv;
}

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

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;
    sq=501;
    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;
    }
    vector<int> ep(sq);
    timer=0;
    setup_euler(0);
    timer++;
    //setup_up(0,ep);
    //setup_down(0);
    for (int i = 0; i < Q; i++)
    {
        int sm=0;
        int e1,e2; cin >> e1>>e2; e1--; e2--;
        vector<pair<int,pair<int,int>>> tos;
        for (int j = 0; j < sz(pr[e1]); j++) {
            int in1=tin[pr[e1][j]], out1=out[pr[e1][j]];
            tos.push_back({in1,{out1,1}});
        }   
        for (int j = 0; j < sz(pr[e2]); j++)
        {
            int in1=tin[pr[e2][j]], out1=out[pr[e2][j]];
            tos.push_back({in1,{out1,2}});

        }
        sort(all(tos));
        ordered_set st;
        int ones=0;
        for (int j = 0; j < sz(tos); j++)
        {
            if(tos[j].second.second==1) {
                ones++;
                int p=tos[j].second.first;
                st.insert(p);
                //cerr << "add " << p << "\n";
            }
            else{
                int r=tos[j].second.first;
                int csum=st.order_of_key(r);
                sm+=ones-csum;
                //cerr << "query " << r <<" for " << csum << " " << ones <<  "\n";

            }
        }
        cerr<<"\n";
        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 2 ms 344 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 10 ms 1368 KB Output is correct
7 Correct 22 ms 1112 KB Output is correct
8 Correct 23 ms 1364 KB Output is correct
9 Correct 47 ms 2384 KB Output is correct
10 Correct 72 ms 2880 KB Output is correct
11 Correct 160 ms 2700 KB Output is correct
12 Correct 190 ms 3964 KB Output is correct
13 Correct 254 ms 3336 KB Output is correct
14 Correct 525 ms 3728 KB Output is correct
15 Correct 579 ms 5800 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8068 ms 8508 KB Time limit exceeded
2 Execution timed out 8077 ms 7596 KB Time limit exceeded
3 Execution timed out 8069 ms 10440 KB Time limit exceeded
4 Correct 469 ms 19044 KB Output is correct
5 Correct 457 ms 24516 KB Output is correct
6 Correct 3359 ms 32860 KB Output is correct
7 Correct 4117 ms 46284 KB Output is correct
8 Correct 3532 ms 50724 KB Output is correct
9 Correct 5523 ms 73504 KB Output is correct
10 Execution timed out 8055 ms 117784 KB Time limit exceeded
11 Execution timed out 8058 ms 114876 KB Time limit exceeded
12 Execution timed out 8069 ms 80648 KB Time limit exceeded
13 Execution timed out 8067 ms 80588 KB Time limit exceeded
14 Execution timed out 8077 ms 96984 KB Time limit exceeded
15 Execution timed out 8042 ms 120272 KB Time limit exceeded
16 Execution timed out 8069 ms 123868 KB Time limit exceeded
17 Execution timed out 8054 ms 102588 KB Time limit exceeded