oj.uz

Submission #1051773

# Submission time Handle Problem Language Result Execution time Memory
1051773 2024-08-10T09:42:34 Z Ludissey Regions (IOI09_regions) C++17
45 / 100
 8000 ms 123812 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 1 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 7 ms 600 KB Output is correct
6 Correct 11 ms 1368 KB Output is correct
7 Correct 18 ms 1112 KB Output is correct
8 Correct 21 ms 1368 KB Output is correct
9 Correct 46 ms 2188 KB Output is correct
10 Correct 68 ms 2648 KB Output is correct
11 Correct 190 ms 2948 KB Output is correct
12 Correct 173 ms 3952 KB Output is correct
13 Correct 242 ms 3588 KB Output is correct
14 Correct 554 ms 3672 KB Output is correct
15 Correct 578 ms 6060 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8080 ms 8632 KB Time limit exceeded
2 Execution timed out 8093 ms 7600 KB Time limit exceeded
3 Execution timed out 8083 ms 10428 KB Time limit exceeded
4 Correct 481 ms 18816 KB Output is correct
5 Correct 452 ms 24524 KB Output is correct
6 Correct 3465 ms 32816 KB Output is correct
7 Correct 4046 ms 46560 KB Output is correct
8 Correct 3600 ms 51208 KB Output is correct
9 Correct 5493 ms 73460 KB Output is correct
10 Execution timed out 8023 ms 117808 KB Time limit exceeded
11 Execution timed out 8042 ms 114864 KB Time limit exceeded
12 Execution timed out 8071 ms 80540 KB Time limit exceeded
13 Execution timed out 8060 ms 80592 KB Time limit exceeded
14 Execution timed out 8076 ms 97056 KB Time limit exceeded
15 Execution timed out 8070 ms 120244 KB Time limit exceeded
16 Execution timed out 8034 ms 123812 KB Time limit exceeded
17 Execution timed out 8032 ms 102588 KB Time limit exceeded