oj.uz

Submission #1051049

# Submission time Handle Problem Language Result Execution time Memory
1051049 2024-08-09T18:54:03 Z Ludissey Regions (IOI09_regions) C++17
75 / 100
 3963 ms 131072 KB 
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;

vector<vector<int>> child;
vector<int> parent;
vector<vector<int>> up;
vector<vector<int>> down;
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++)
        {
            down[conv[rg[x]]][i]+=v[i];
            cv[i]+=v[i];
        }
    }
    if(conv[rg[x]]<sq){
        down[conv[rg[x]]][conv[rg[x]]]++;
        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]+=rm[i];
    }
    if(conv[rg[x]]<sq){
        up[conv[rg[x]]][conv[rg[x]]]++;
        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=500;
    child.resize(N);
    parent.resize(N);
    up.resize(R,vector<int>(sq));
    down.resize(R,vector<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);
    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--;
        if(conv[e1]<sq){
            sm=up[conv[e2]][conv[e1]];
        }else if(conv[e2]<sq) {
            sm=down[conv[e1]][conv[e2]];
        }else{

            vector<pair<int,pair<int,int>>> tos;
            vector<int> forCONV;
            unordered_map<int,int> conv2;
            for (int j = 0; j < sz(pr[e1]); j++)
            {
                int in1=tin[pr[e1][j]], out1=out[pr[e1][j]];
                forCONV.push_back(in1);
                forCONV.push_back(out1);
            }   
            for (int j = 0; j < sz(pr[e2]); j++)
            {
                int in1=tin[pr[e2][j]], out1=out[pr[e2][j]];
                forCONV.push_back(in1);
                forCONV.push_back(out1);
            }
            sort(all(forCONV));
            for (int j = 0; j < sz(forCONV); j++)
            {
                conv2[forCONV[j]]=j;
            }
            
            for (int j = 0; j < sz(pr[e1]); j++)
            {
                int in1=tin[pr[e1][j]], out1=out[pr[e1][j]];
                tos.push_back({conv2[in1],{conv2[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({conv2[in1],{conv2[out1],2}});
            }
            sort(all(tos));
            vector<int> t;
            t.resize(sz(forCONV)*2+1,0);
            int ones=0;
            for (int j = 0; j < sz(tos); j++)
            {
                if(tos[j].second.second==1) {
                    ones++;
                    int p=tos[j].second.first;
                    int value=1;
                    for (t[p += sz(forCONV)] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
                }
                else{
                    int csum=0;
                    int l=0;
                    int r=tos[j].second.first+1;
                    for (l += sz(forCONV), r += sz(forCONV); l < r; l >>= 1, r >>= 1) {
                        if (l&1) csum += t[l++];
                        if (r&1) csum += t[--r];
                    }
                    sm+=ones-csum;
                }
            }
        }
        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 3 ms 600 KB Output is correct
5 Correct 7 ms 908 KB Output is correct
6 Correct 16 ms 3160 KB Output is correct
7 Correct 28 ms 1420 KB Output is correct
8 Correct 33 ms 1980 KB Output is correct
9 Correct 80 ms 12388 KB Output is correct
10 Correct 107 ms 3160 KB Output is correct
11 Correct 175 ms 3984 KB Output is correct
12 Correct 295 ms 12988 KB Output is correct
13 Correct 252 ms 3416 KB Output is correct
14 Correct 312 ms 3892 KB Output is correct
15 Correct 557 ms 88372 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1202 ms 37804 KB Output is correct
2 Correct 1138 ms 10636 KB Output is correct
3 Correct 1680 ms 81396 KB Output is correct
4 Correct 422 ms 22276 KB Output is correct
5 Correct 619 ms 76480 KB Output is correct
6 Correct 846 ms 44124 KB Output is correct
7 Correct 1148 ms 56180 KB Output is correct
8 Runtime error 322 ms 131072 KB Execution killed with signal 9
9 Correct 2412 ms 111572 KB Output is correct
10 Runtime error 94 ms 131072 KB Execution killed with signal 9
11 Correct 3963 ms 121056 KB Output is correct
12 Correct 2493 ms 86960 KB Output is correct
13 Correct 2715 ms 119260 KB Output is correct
14 Correct 2824 ms 112128 KB Output is correct
15 Runtime error 96 ms 131072 KB Execution killed with signal 9
16 Runtime error 112 ms 131072 KB Execution killed with signal 9
17 Runtime error 156 ms 131072 KB Execution killed with signal 9