oj.uz

답안 #1051799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1051799 2024-08-10T09:51:09 Z Ludissey Regions (IOI09_regions) C++17
75 / 100
 8000 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;
    sq=sqrt(R);
    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_down(0,ep);
    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{
            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

# 결과 실행 시간 메모리 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 8 ms 600 KB Output is correct
7 Correct 14 ms 600 KB Output is correct
8 Correct 17 ms 600 KB Output is correct
9 Correct 28 ms 2392 KB Output is correct
10 Correct 55 ms 1368 KB Output is correct
11 Correct 144 ms 1624 KB Output is correct
12 Correct 166 ms 3672 KB Output is correct
13 Correct 200 ms 1880 KB Output is correct
14 Correct 436 ms 2648 KB Output is correct
15 Correct 476 ms 16752 KB Output is correct

Subtask #2
60.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2126 ms 10484 KB Output is correct
2 Correct 2105 ms 6216 KB Output is correct
3 Correct 4524 ms 18776 KB Output is correct
4 Correct 277 ms 6212 KB Output is correct
5 Correct 352 ms 25092 KB Output is correct
6 Correct 393 ms 14180 KB Output is correct
7 Correct 650 ms 19160 KB Output is correct
8 Correct 946 ms 84176 KB Output is correct
9 Correct 2484 ms 48908 KB Output is correct
10 Runtime error 273 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8082 ms 51232 KB Time limit exceeded
12 Correct 1840 ms 36348 KB Output is correct
13 Correct 2635 ms 54176 KB Output is correct
14 Correct 2369 ms 48908 KB Output is correct
15 Runtime error 184 ms 131072 KB Execution killed with signal 9
16 Runtime error 133 ms 131072 KB Execution killed with signal 9
17 Runtime error 160 ms 131072 KB Execution killed with signal 9