oj.uz

Submission #1051802

# Submission time Handle Problem Language Result Execution time Memory
1051802 2024-08-10T09:53:04 Z Ludissey Regions (IOI09_regions) C++17
45 / 100
 8000 ms 123820 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";
 
            }
        }
        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 600 KB Output is correct
6 Correct 8 ms 1520 KB Output is correct
7 Correct 20 ms 1112 KB Output is correct
8 Correct 18 ms 1368 KB Output is correct
9 Correct 30 ms 2136 KB Output is correct
10 Correct 64 ms 2648 KB Output is correct
11 Correct 145 ms 2644 KB Output is correct
12 Correct 162 ms 3960 KB Output is correct
13 Correct 238 ms 3160 KB Output is correct
14 Correct 491 ms 3416 KB Output is correct
15 Correct 544 ms 5780 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8093 ms 8464 KB Time limit exceeded
2 Execution timed out 8067 ms 7512 KB Time limit exceeded
3 Execution timed out 8021 ms 10332 KB Time limit exceeded
4 Correct 427 ms 18776 KB Output is correct
5 Correct 446 ms 24240 KB Output is correct
6 Correct 3486 ms 32564 KB Output is correct
7 Correct 3975 ms 45972 KB Output is correct
8 Correct 3559 ms 50640 KB Output is correct
9 Correct 5450 ms 72896 KB Output is correct
10 Execution timed out 8016 ms 117200 KB Time limit exceeded
11 Execution timed out 8055 ms 114296 KB Time limit exceeded
12 Execution timed out 8052 ms 80592 KB Time limit exceeded
13 Execution timed out 8080 ms 80548 KB Time limit exceeded
14 Execution timed out 8047 ms 96980 KB Time limit exceeded
15 Execution timed out 8048 ms 120432 KB Time limit exceeded
16 Execution timed out 8080 ms 123820 KB Time limit exceeded
17 Execution timed out 8066 ms 102460 KB Time limit exceeded